Python3 – 対数

Pythonで対数を出すには、math.logを使います。import mathで使えるようになります。

0.30102999566398114

これは、10を何乗したら2になるか?です。log102です。
試しに、10を0.30102999566398114乗してみます。

1.9999999999999998

100の0.5乗は、100の平方根なので10です。

10.0

27の0.3333333333333333333333333333333333333333333乗は、大体27の立方根なので、3に近いはずです。

3.0

おージャスト3.0になった。

2.9999999999999964

3.0

少数15桁までだと2.99…になりますが、16桁にするとジャスト3.0になる。

10を底とする対数を常用対数といいます。

対数関数と指数関数は逆関数の関係にあります。逆関数はy=xに対して対称です。指数関数と対数関数のグラフを書いてみます。
y = axの指数関数と、y = logaxの対数関数を書きます。

numpyを使いたいので、math.logではなくnp.logを使います。aを2として、np.log2を使います。例えばnp.log2(4)とすると2になります。2を底とした4の対数を出しています。

対称なのか全然これじゃ分からない。

対数関数は、
対数が1より小さいとき、
底が1より大きければ、真数は底より小さい。
底が1より小さければ、真数は底より大きくなる。

対数関数を、底の大きさのパターンで2つ書いてみる。

2100の桁数を出すには、常用対数を使います。
log102100 = 100log102 = 100 * 0.30102999566398114 = 30.102999566398114
よって31桁です。10の2乗は100なので3桁です。10の3乗は1000で4桁です。2.1乗は100より大きく、1000より小さいので3桁です。30.10乗は31桁です。

Python3 – xのn乗のグラフ(matplotlibのsubplotとアニメーション)

GIFアニメーション

matplotlibのアニメーション作成は2つ種類があって、ArtistAnimationとFuncAnimationとがある。

参考:matplotlib でアニメーションを作る

ArtistAnimation は、あらかじめ全てのグラフを配列の形で用意しておき、それを1枚ずつ流すというものである。FuncAnimationは予め完成したグラフを渡すのではなく、アニメーションの1フレームごとに関数を実行する。データが巨大すぎる場合や潜在的に無限に続く場合に便利。

ArtistAnimation

ArtistAnimationを使って、xの2乗~10乗のグラフを配列に入れて、アニメーションをつくってみる。

サンプルコード

結果

これだと、10乗のグラフのyが大きすぎて、他がみんな直線みたいになってしまった。

FuncAnimation

FuncAnimationを使ってやってみる。

結果

指数が偶数ならy軸に対称のグラフになり、奇数なら原点に対象のグラフになります。原点に対象っていうのか。

Subplot

matplotlibで複数のグラフを表示したいときにsubplotが使えます。
参考:[Python]Matplotlibで複数のグラフを描画する方法

サンプルコード

結果

Python3 – 変数のスコープについて

下記コードのとき結果は1と表示されます。

下記コードのときエラーになります。

UnboundLocalError: local variable ‘n’ referenced before assignment

参考:なぜ変数に値があるのに UnboundLocalError が出るのですか?

これは、あるスコープの中で変数に代入を行うとき、その変数はそのスコープに対してローカルになり、外のスコープにある同じ名前の変数を隠すからです。foo の最後の文が x に新しい値を代入しているので、コンパイラはこれをローカル変数であると認識します。その結果、先の print(x) が初期化されていないローカル変数を表示しようとして結果はエラーとなります。

globalだよと宣言すると大丈夫になります。

ネストされたスコープだと、nonlocalが使えます。

Python3 – matplotlibでアニメーションGIFをつくる

matplotlib.animatioを使うとアニメーションがつくれます。自分の環境ではgifで保存しようとしたら、imagemagickがなくてエラーになりました。imagemagickのインストールとかはここに書いてありました。

Imagemagick

http://www.imagemagick.org/script/binary-releases.php#windows

Imagemagickのパスをmatplotlibに設定する必要がある。下記のようにするとmatplotlibが見ている設定ファイルの場所がわかる。

自分はユーザディレクトリ内のAnaconda3の中の下記だった。

matplotlibrcの最後の行らへんに、下記行があるので、ここにImagemagickのパスを入れる。

コメントを外して、下記のように入力します。入力の際、パスを「’」で囲むと下記のようなエラーになります。


C:\Users\hoge\Anaconda3\lib\site-packages\matplotlib\animation.py:782: UserWarning: MovieWriter imagemagick unavailable
warnings.warn(“MovieWriter %s unavailable” % writer)
Traceback (most recent call last):
File “C:/Users/hoge/hoge.py”, line 15, in
ani.save(‘sample.gif’, writer=’imagemagick’)
File “C:\Users\hoge\Anaconda3\lib\site-packages\matplotlib\animation.py”, line 810, in save
writer.grab_frame(**savefig_kwargs)
File “C:\Users\hoge\Anaconda3\lib\contextlib.py”, line 66, in __exit__
next(self.gen)
File “C:\Users\hoge\Anaconda3\lib\site-packages\matplotlib\animation.py”, line 196, in saving
self.finish()
File “C:\Users\hoge\Anaconda3\lib\site-packages\matplotlib\animation.py”, line 389, in finish
+ ‘ Try running with –verbose-debug’)
RuntimeError: Error creating movie, return code: 1 Try running with –verbose-debug

サンプルコード

Python3 – 素因数分解

素因数分解

正の整数 n を素因数分解するための最も単純な方法は、2 から順に √n までの素数で割っていく方法である(Trial division(英語版))。しかし、n が大きくなると、この方法では困難である。

結果
[3, 79, 519507173]

参考:Python Finding Prime Factors

Python3 – timeitを使ってコマンドライン上で関数の実行速度を計る

コマンドラインで実行できるので、プログラムに計測用のコードを書かなくてよくて便利。

timeit — 小さなコード断片の実行時間計測

計測方法

自分の環境だと、実行したいpythonファイル(hoge.py)がおいてあるディレクトリで、下記のようにやると動きます。(hoge.pyのtest関数の実行速度を計測したい場合)

計測結果の見方

試しに、ここで作成した素数を出すコードの速度を計測してみます。ファイル名は、eratos.pyです。

結果

結果の見方がややこしい。
参考:ライブラリ:timeit

-nは、1試行あたりの実行回数。-rは試行回数らしい。下記のように指定できる。

上記の場合は、処理を10回連続で実行したときの時間を5回計測し、そのうちの最小時間を返してくれているらしい。デフォルトだと連続で100回実行して、ランダムなタイミング(?)で3回だけ時間を計測して、3回のうち一番時間が短かった結果を返してくれているということかな?まあ何しろこれで実行時間が簡単に計測できるので便利です。

時間の単位は、下記になります。

単位名 単位
ナノ秒 1,000,000,000 nsec(ns) 10の-9乗 s
マイクロ秒 1,000,000 usec(µs) 10の-6乗 s
ミリ秒 1,000 msec(ms) 10の-3乗 s
1 sec(s) 1s

Python3 – 素数

エラトステネスの篩

エラトステネスの篩

結果
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

参考:素数と仲良しになる3つのプログラム

フェルマーの小定理

フェルマーの小定理で素数か判定できる。

Pythonを使って高速素数判定をしてみる」に詳しく書いてあった。フェルマーテストというので出せるけど、素数じゃないものも出しちゃう可能性があって、より高性能な方法がある。それもこのサイトに書いてある。

Let’s Encryptの更新方法と更新の自動化

この投稿でLet’s Encryptで無料でSSL証明書を作りましたが有効期限が切れそうなので更新します。
環境は、サーバはさくらのVPS、OSはUbuntu16.04、webサーバはnginxです。

更新方法

参考:https://certbot.eff.org/#ubuntuxenial-nginx

Automating renewal

有効期限が切れる前に自動的に証明書を更新するようにCertbotを設定することができます。 Let’s Encrypt Encryptは90日間使用できるので、この機能を利用することをお勧めします。このコマンドを実行すると、証明書の自動更新をテストできます。

Ubuntu Xenial上のCertbotのバージョンに「電子メールなしで登録する!」という警告が表示されるバグがあります。以前にCertbotに電子メールを送っていたとしても。これが起こっても心配しないでください。更新には影響しません。それが正しく動作していると思われる場合は、以下を実行するcronまたはsystemdジョブを追加して自動更新を手配できます

更新する

更新はNginxをとめないといけません。止めずにrenewコマンドを実行すると、エラーがでます。

手動で更新する

Nginxを停止したのちに、renewコマンドを実行して、Nginxを再開するか、webrootプラグインを利用して、renewコマンドを実行する必要があります。webrootプラグインを利用する場合、80ポートにアクセスしてNot Foundとかにならないようにする必要があるようです。私の場合、httpsでしか接続できない(httpの場合強制的にhttpsにリダイレクトさせる)ようにしてあるので、webrootは使えませんでした。Nginx停止&再開をrenewコマンドの前後でやってみます。

自動更新させる

自動更新はcronを使います。

.crontabの中身を下記のようにします。

あるいは、ログを残しておく場合は下記のようにします。

crontabに反映させます。

設定がうまく反映できているかの確認をしたい場合、一旦上記cronの実行頻度を変更してすぐに実行させるようにしつつ、下記のような感じでログ出力したらいいと思います。

Ubuntu – cron

Ubuntu16.04です。

cronを使うには、crontabコマンドを使います。
crontab -e とやるとcronの編集ができますが、cron -rとやるとcronの設定内容が消えるので、危ないので気を付けるようにとネットでよく書いてあります。紹介されているのは、crontab -eで直接編集するのではなく、別ファイルでcron内容を作成・編集してcrontabで読み込むことです。

これで.crontabに書いた設定が反映されます。
ubuntu16.04の場合、cronの実行ログはデフォルトでは表示されないぽいです。またログの表示設定をしても、デフォルトでは、/var/log/cron.logは出力されず、/var/log/syslogに出力されるようです。実行ログのみでエラー内容や標準出力はログには残りません。/var/log/syslogにcronログを出力させるには、下記ファイルのcron関連のコメントを外してrsyslogを再起動します。

cronで実行結果をログに出力させるには、下記のようにします。
.crontab

2>&1の2は標準エラー出力、1は標準出力です。2を標準出力にリダイレクトさせることによって、エラーも出力されます。

複数コマンドを実行する場合、;か&&でつなげます。;は、前のコマンドがエラーでも次を実行します。&&はエラーだったら次を実行しません。複数コマンドを1行でつなげた場合、例えば下記のようにやっても最後のコマンドの出力以外は受け取れません。

下記のようにすると、最初のコマンドのエラーも含めた出力がファイルに保存されます。

下記なら、最初のechoに誤字があるので、その時点でエラーで終了し、エラー内容がファイルに出力されます。

Python3 – Seleniumの使い方

Selenium
http://www.seleniumhq.org/

作業環境

私の環境は、下記です。
Windows10
Python3.5
Firefox 51.0.1
Chrome 56.0
ChromeDriver 2.27

Selenium WebDriver

SeleniumRCはJavascriptでブラウザを操作してたけどセキュリティ的に難しくなってSelenium WebDriverが主流になったそうです。WebDriverはブラウザの拡張機能やOSのネイティブ機能などを利用して操作するそうです。ブラウザのドライバに対して、JSON Wire ProtocolでHTTPリクエストを行うとブラウザが操作できるます。ドライバは各ブラウザ毎に異なります。

ドライバに対するリクエストは、一般的には各種プログラミング言語で作成します。使える言語は、公式だと、Java、Ruby、Python、C#、Javascript、PHP、Perlだそうです。その他非公式であったりするそうです。私はPythonでやってみようかなと思います。

Python用Seleniumモジュールをインストールする

pipでインストールできます。

Python用のseleniumのAPIのドキュメントはここです。

chromeドライバのインストールと設定

Chrome Driverはこのページでダウンロードできます。ChromeDriver 2.27のchromedriver_win32.zipをダウンロードしました。展開して、chromedriver.exeを任意のフォルダに配置し、そのフォルダにパスを通しておきます。

Fireboxドライバのインストールと設定

Firefoxはブラウザをインストールしてあればドライバが使えると色々なところに書いてはあったのですが、Firefoxの新しいバージョンではそうでもないらしく、実際自分もエラーになってしまいました。下記のようなエラーが出る場合、ドライバが有効になっていない可能性があります。

上記のような場合は、ここからドライバをダウンロードしてみます。私は、geckodriver-v0.14.0-win64.zipをダウンロードして展開して、上記のchromeと同様に任意のフォルダにgeckodriver.exeを配置し、そのフォルダにパスを通しました。これで、Firefoxも動作するようになりました。

PythonでSeleniumを操作してみる

ブラウザを起動してURLを開く

要素の選択、入力、クリック

Googleに検索ワードを入力して検索ボタンを押すことで検索結果ページに遷移させてみます。

chromeの場合は、検索ワードを入力したら勝手に検索結果のページに遷移したので、btnを取得・クリックしていません。

ログイン

上記と同じですが、ログインもしてみます。Twitterにログインします。

問題なくログインできるのですが、getでURLを開くと全て読み込むまで次に進まないようで、ログインボタンをクリックするまでにやたらと待たせれる点がいやです。解決方法があるか今度確認します。

参考:
第1回 Seleniumの仕組み
Seleniumとは―読み方、意味、WebDriverの使い方
Selenium Web DriverのPythonバインディングを使ってブラウザを操作する
5分でわかるSelenium IDEの使い方
Python で Selenium WebDriver を使ったブラウザテストをする方法
Webブラウザの自動操作 (Selenium with Rubyの実例集)

Python3 – アルゴリズム(重み付きグラフ・最短経路探索・ダイクストラのアルゴリズム)

参考:欲張り法 (greedy strategy)

重み付きグラフ

networkxでつくった重みグラフ

networkxのコードサンプル

上記は重み付きのグラフです。これはnetworkxで書きました。コードは下記です。

この重み付きグラフは参考サイトにのってるやつです。参考サイトのダイクストラのアルゴリズムをやってみます。

ダイクストラのアルゴリズム

重み付きグラフの最短経路探索のアルゴリズムの一つです。効率は結構いいですが、各地点のコストに負の値があると使えません。

コードサンプル

結果

上記はfからbまでの最短経路を探しております。どういう動きなのかを言葉で書くのが難しい。。

アルゴリズムの仕組み

最初にする主なこと

・スタート地点のコストを0にする。
・現在地をスタート地点にする。

ループでしている主なこと

・現在地を訪問済み(チェック済み)にする。
・現在地から訪問可能な地点の、各コスト(現在地までのコスト+現在地から訪問可能地点までのコスト)を出して、今まで記憶しているコストより低ければ更新する。
・訪問済みでない地点の記憶されているコストで最も低いコストの地点を現在地にする。
・以降、上記3つを繰り返す。
・訪問済みの地点がなくなったらループを終了させる。

ループ終了後どうなっているか?

・スタート地点からの各地点までの最短コストと、パスを記憶している。上記コードの場合、cost配列にコストが入っていて、prev配列に各地点の直前の地点が入っている。

注意点

・各地点のコストがマイナスのものがあるとこのアルゴリズムは使えない。

改善点

・ヒープを使うとより効率的になるらしいので、次にヒープを使ってつくってみる。
・最短経路をnetworkxで表示させるようにしたい。

Python3 – ヒープをnetworkxではなくgraphvizで書いてみる

networkxだときれいに表示できない。posに表示スタイルを設定するようですが、spring_layout、spectral_layout、shell_layoutとかありますが、全部キレイな木を表示してくれる感じじゃない。外部のdotファイルとかいうのを読み込むとできるようですが、graphvizというのがあるので、そっちをやってみます。

Networkxの場合

Graphvizの場合

インストール

ここからGraphvizをダウンロードしてインストールします。
その後、下記のようにpipインストールします。

あと、windows10ですが、pathを通す必要がありました。インストールしたフォルダのbinをフォルダのパスを通してください。

サンプルコード

参考:graphvizを使ってPython3で木構造を描く

Python3 – ヒープ

ヒープはノードに常に子供が2個あって、子供より親は小さい値を持ちます。ヒープは配列で表せます。配列の0番目は一番上の根ノードです。あとは、k番目のノードの子供は、左が2k+1、右が2k+2番目になります。挿入は最後に挿入して、親ノードと比較して必要に応じて交換することを繰り返します。

Python3にはヒープのデータ構造がデフォルトで用意されているようなので、使ってみます。heapqです。これはヒープキュー、優先度キュー、プライオリティキューとかいわれるものみたいで、「優先度が高い順に取り出せるデータ構造」だそうです。(参考:優先度キュー

普通の配列をヒープにする

コード

結果

コード

結果

ヒープに挿入する

結果

ヒープからpopする

結果

heappushpopはpushしてから、popする。heappushしてからheappopするよりも効率的だそうです。pushしてからpopするので、pushしたものも含めて最小値をpopします。heapreplaceはpopしてからpushするので、pushした要素が最小値でもpopされません。

Python3 – アルゴリズム(グラフ)

参考:http://www.geocities.jp/m_Hiroi/light/pyalgo05.html

グラフをプログラムする場合、よく使われる方法に「隣接行列」と「隣接リスト」があります。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行列で表すことができます。

グラフの例

グラフをプログラムで書く

隣接行列

縦横がそれぞれa-gまでのノードを表す。エッジがある場合は1にする。g[0][1]は、a-b間のエッジがあることを示す。

隣接行列の欠点は、辺の数が少ない場合でも N 行 N 列の行列が必要になることです。つまり、ほとんどの要素が 0 になってしまい、メモリを浪費してしまうのです。この欠点を補う方法に隣接リストがあります。これはつながっている頂点を格納する方法です。

隣接リスト

つながってる頂点を配列にいれる。

探索

深さ優先探索

使い方

結果

再帰をうまく使うと芸術的だな。分かりづらいけど。goalは到達したい場所。pathはスタート地点と通過したい場所を配列で入れる。
AからGに行きたい場合は、search(6, [0])という風にやります。最初にpathの最後の要素を取り出しそれがゴール地点だったら、pathつまりスタート地点からゴール地点までの順番を表示しております。ゴール地点でなければ、現在位置からいける地点を順に取り出し、pathに加えます。その際に、戻らないように今まで通った場所は、次にいける地点から除外します。そして、またsearch(goal, path)を実行します。再帰的に繰り返すことで、Goalに到達可能であれば、いずれGoalが次にいける地点に現れます。これによって、goalへの道順を発見できたことになります。最後のsearchの実行で、pathがprintされます。これで最後のsearchは終了します。もしゴールに到達できなければ、最終的にはg[n]が空になるか、if x not in pathにマッチしないものだけになるか、になるので、これもまた最後のsearchは終了します。そうすると1個前のsearchの後のpopによってpathが1つ前の状態に戻り、forが残ってたら残りのforを回すし、なければ終わりになって、もう1つ前のsearchの実行に戻りまっす。まあ文章で書いてもめちゃくちゃになるけど。再帰を自分でパッと思いつけるようになるのは結構大変だろうな。

これが深さ優先探索といわれるのは、到達可能な深い場所にとりあえずどんどんいって、また戻っては次にいける深いところにどんどん行くことを繰り返すからだと思います。最短経路探索と言われているものをしようとしても、全部やってみて一番短いやつを選択することになるので、いけるところは全部見る必要があるのかなと思います。

幅優先探索

幅優先探索は、最短経路探索に適していて深さ優先探索より効率的だそうです。ただし、深さ優先の場合は諸突猛進型でとりあえず一番深いところまで行って終わったら、戻ってきて、もう今までのことは忘れるのですが、幅優先の場合は、全ての経路を並行して深堀っていきます。そのため、最短経路が発見されるまで全ての経路の道順を記憶しておく必要があり、メモリの必要量が深さ優先に比べて圧倒的に多くなる可能性があります。でも、ものすごい深いグラフだと深さ優先グラフでもメモリが膨大になる可能性があります。

使い方

結果

qをキューとして使っている。先入れ先出ししている。先入れ先出し。このqで全部の経路を記憶しており、最初に記憶したものは階層が低いパスになるので、最初に記憶したものから順番に取り出している。qがからになるまでwhileを続けている。popで一番古いパスを取り出して、そのパスの最後尾がゴールだったらprintで経路を書き出している。ゴールでない場合、現在地から次にいける地点を取り出して、順番に処理している。処理内容は、単純に今までの経路に取り出した次にいける地点を追加したものを、qに加えているだけ。

このキューをスタックにすると、深さ優先探索になるらしいのでやってみる。

深さ優先探索のwhileバージョン

こういうことでしょうか?キューは先入れ先出し、スタックは後入れ先出。qに入っているものをpop()で末尾から取り出せば、後入れ先出になる。とりあえず全部探索できるし、結果もあってるんだけど、最初に再帰でやったやつとは出力順序が異なる。これは、再帰でやったやつは、各配列の先頭から深堀していくのに対して、whileの場合は、配列の末尾から深堀していくから。メモリ的には再帰でやった方がいいんじゃないかと思う。再帰の場合記憶しているのは一つの経路だけだから。

反復深化

反復深化というのは、深さ優先の深堀する最大階層を決めるやつ。1階層目まででまず深さ優先をやって、ダメだったら2階層目まででやるという感じで進めていく。必要となるメモリ量は深さ優先と同じになるので、幅優先と比べるとメモリ使用量は少ない。ただし、1階層目でだめだったら、2階層目までの制限で再度一からやり直すことになり、同じ探索を何度もすることになるため、時間的には無駄が多く効率が悪い。

結果