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

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階層目までの制限で再度一からやり直すことになり、同じ探索を何度もすることになるため、時間的には無駄が多く効率が悪い。

結果

Python3 – NetworkXでグラフを表示する

https://networkx.github.io/

インストール

https://github.com/networkx/networkx/

Decoratorというのも必要っぽい。両方ともすでに入ってた。

サンプルコード

結果

使い方

matplotlibでグラフを表示する

https://networkx.readthedocs.io/en/stable/tutorial/tutorial.html

サンプルコード

参考:
[Python]NetworkXでQiitaのタグ関係図を描く
Pythonで迷路を解く – アルゴリズムクイックリファレンス6章の補足 –
NetworkXでグラフを描いた(最短経路他)

Python3 – アルゴリズム(累乗)・計算量

累乗

pow0は遅いやつ。計算量はループをn回回すので、O(n)という。pow1は速いやつ。計算量はO(log n)らしい。

ちなみに、自分のPCで速度を計ったら、下記だった。(python3内蔵のpow関数は、pow1と同じ速度だった)
print(pow0(2, 1000000))は17.3秒
print(pow1(2, 1000000))は1.3秒

なんで、pow1の計算量はO(log n)なのか?

pow1を呼び出す度に、nを半分にしている(2のマイナス1乗を掛けてる)。nを2のk乗とおくと、pow1の呼び出し回数は、k回となる。よってO(k)となる、n = 2のk乗だから、k = log2 n。O()表記の場合、対数の底は無視するので、log n。

参考:
再帰定義 (recursive definition)
[初心者向け] プログラムの計算量を求める方法

Python3 – 動的計画法(フィボナッチ数列)

動的計画法は、分割統治法メモ化を合わせた方法のことらしい。分割統治法は、問題を細分化して、細かい部分を順に解いていくことで全体を解明するようなことの総称らしい。

分割統治法は、コード的には下記のようになり、再帰することになる。

メモ化とは、再帰の際に同じ副問題を複数回解いてしまうことによる効率低下を防ぐために、副問題の結果を保存して再利用することらしい。キャッシュみたいな感じ。

下記のフィボナッチ数列を表示するプログラムは、動的計画法の具体的な例らしい。

Python3だと下記のような感じ。

ちなみに、ネットでフィボナッチ数列のPython版しらべたら下記がでてきたけど、これはまさしく動的計画法じゃない例だと思った。毎回メモらずに計算しているようだ。

せっかくだから時間図ってみる。

結果

おー40倍速いってことか。さすが動的計画法だ。

下記のような方法もある。

greedyアルゴリズム(貪欲法)

greedyアルゴリズムは、全部をN回試して、報酬の平均が最も高いやつを選択するというアルゴリズムです。

当たりか外れがでる機械が4個あって、どれが一番当たり率が高いか分からないのでgreedyアルゴリズムでやってみる想定にします。機械はa~dまであってそれぞれ当たり率は下記のとおりとします。

a b c d
0.3 0.6 0.8 0.95

当たりが出たら1点もらえて、外れたら0点とします。

結果

Python3 – random

randomを試してみます。

下記をやってみます。100回randintを0~100まででやってみます。

結果

10000回やってみます。

100000回やってみます。

100万回やってみます。

seed設定してみます。

何回やっても、下記でした。

何回やっても下記でした。

seedが同じだと、プログラムを実行する度に、まったく同じ数字が同じ順番ででてくる。

60%の確率で正解を出す機械をつくってみます。
random.random()が0.6以内だったら当たりにします。

結果

手書き文字を作れるJavascriptをつくってTensorFlowで予測させてみた(2)

この前、「手書き文字を作れるJavascriptをつくってTensorFlowで予測させてみた」という投稿でブラウザ上で手書きした文字画像を、MNISTで訓練したモデルで予測してみましたが、ものすごく精度が悪かったです。今回改めて、CNNを使ってやってみたらかなり精度が上がりました。何%か測ったりしてませんが、自分の手書きだと90%は超える感じでした。やっぱりCNNはすごいなーと思いました。でももしかしたら前回のものにミスがあり、CNNではなくても精度は本当はもっと高い可能性はあります。

もうちょっとやるとしたら、文字を画像の中心に適度な大きさで書く必要があり、例えば右上に小さく2と書いても認識されません。あとは、現在はMNISTに合わせて、手書き文字画像も背景黒、文字色白で作成するように固定していますが、これらの色を変えても認識するようにしたいです。今度やってみます。

Github

https://github.com/endoyuta/mnist_test

index.html

cgi-bin/mnist.py

cgi-bin/mytensor.py

TensorFlow – Local Response Normalization(LRN)(局所的応答正規化)

参考:theanoで局所コントラスト正規化(Local Contrast Normalization)を使う

正規化の方法にはいろいろあり、代表的なものを挙げると

Global Contrast Normalization(GCN)
Local Contrast Normalization(LCN)
Local Response Normalization(LRN)
ZCA whitening
Local mean subtraction

CNN内の正規化層としては、LCNやらLRNが使われる。

LCNはその名の通り、特徴マップの局所領域内でコントラストを正規化する。この処理は一つの特徴マップ内で完結するので、すべての特徴マップに対して独立して行う。
対してLRNでは、同一位置における異なる特徴マップ間で正規化する。どちらもいくつかのハイパーパラメータはあるが、学習の対象となるパラメータはないので、誤差伝播が容易に可能である。

参考:theanoでLocal Response Normalization(LRN)を使う

LRNは端的に述べると、「同一位置(ピクセル)において複数の特徴マップ間で正規化する」ということだそうだ。元の論文にも書いてあるが、LRNは”brightness normalization”であり、LCNのように輝度の平均を減算して0にしないことがミソらしい。


$$\displaystyle
b^i_{x,y}=a^i_{x,y}/ \left( k+\alpha \sum^{min(N-1,i+\frac{n}{2})}_{j=max(0,i-\frac{n}{2})} (a^j_{x,y})^2 \right)^\beta
$$

k, n, α, βがパラメータである{a^i_{x,y}}はi番目の特徴マップの(x,y)のピクセルを、Nは特徴マップの総数を表す。
summationの部分は、「i番目の特徴マップに対して、n近傍の特徴マップの二乗和をとる」という意味である。

参考:tf.nn.local_response_normalization(input, depth_radius=None, bias=None, alpha=None, beta=None, name=None)

Local Response Normalization.

The 4-D input tensor is treated as a 3-D array of 1-D vectors (along the last dimension), and each vector is normalized independently. Within a given vector, each component is divided by the weighted, squared sum of inputs within depth_radius. In detail,

翻訳結果

4次元入力テンソルは、(最後の次元に沿って)1次元ベクトルの3次元配列として扱われ、各ベクトルは独立して正規化されます。 所与のベクトル内で、各成分は、depth_radius内の入力の加重二乗和で除算される。

使用例

Python3で関数をつくってみる

使ってみる

結果

tf.nn.lrnを使ってみる

コード

結果

おーほぼほぼ同じだ。適当な別の配列でも試してみよう。

適当な配列でも試してみる

適当な配列

結果

自作関数の結果

tf.nn.lrnの結果

ほぼ同じ。

大きい写真にLRNをしてみて結果をみてみる

画像はこれです。

コード

結果

これをCNNに入れ込むと効果が高まるって気づいた人すごいっす。

Python3 – NumpyとPythonの配列のスライスでマイナス使った場合

  • 開始位置より終了位置が小さい場合は空。
  • マイナスの場合、後ろから数える。一番最後が-1。
  • 終了位置が実際の配列の最後より大きい場合は、実際の配列の最後になる。
  • 開始位置は0だったら0番目も含まれるが、終了位置が例えば10だった場合、9番目までが含まれる。
  • 終了位置が-1だったら、-2までが含まれる。

コード

結果