良いもの。悪いもの。

先週ぐらいから クッキークリッカー(Cookie Clicker) というJavaScriptを使ったブラウザゲームが流行っている。クリックするだけのゲームと聞いて、最初はあまり興味を持てなかったのだが、自分の周りであまりにもやっている人が多いので少し遊んでみることにした。 クッキークリッカーを簡単に説明すると、まずはクリックすることでクッキーを作り、作ったクッキーを使ってクッキーの生産性を高めるためのアップグレードやアイテムを購入し、たまに出現するゴールデンクッキー(Golden Cookie)をクリックすることでさらに多量のクッキーが得られるので、それらを駆使してできるだけたくさんのクッキーを作るというゲームだ。 このようにとてもシンプルなゲームなのだが、最初はちまちまとしか作れなかったクッキーが徐々に増えていき、様々なアイテムやイベントを通すことで、終盤では毎秒数千億クッキーを作れるというところに人々を惹きつける魅力があるらしい。しかし、自分は「人間の代わりにプログラムを働かせることでどこまで効率が良くなるか」という目的のために自動化プログラムを作成したくなった。コンピュータは人間を楽にさせるために存在するべきだ。 このゲームはJavaScriptで作られており、そのコードや変数を修正すれば簡単にチートを行うことができる。しかし、自分はそれについては全く興味がない。元のシステムには全く手を入れずに人間が操作する部分のみをプログラムで最適化したいのだ。 まず、最初に考えついたのは自動クリックだ。これは様々なツールが世に溢れているのでそれを使っても良いのだが、プログラマだったら、このぐらいは自分で作りたい。そこで、Pythonと pymouse を使って自動クリックプログラムを作成した。これで、毎秒100～200クリックすることができるようになった。これ以上の速度にするとブラウザがついて行けずプチフリーズを頻繁に起こし逆に生産性が落ちてしまう。因みに画面上のエフェクトなどは設定で消しておくほうが良いだろう。 次に、ゴールデンクッキーへの対処だ。ゴールデンクッキーはランダムな間隔でブラウザ上のどこかに出現する。そのクッキーをクリックすると溜まっているクッキーの1割分の枚数が貰えたり、一定時間現在の7倍の効率でクッキーを焼けるようになったりする。...

世の中のことをもっと知るにはどうしたら良いだろうと思うときがある。世の中の多くの事柄はログやデータに落とされる。Googleなどの検索サイトは良い例だろう。さて、そのログやデータをどうすれば良いのか? 多くの場合、視覚化が有効な手段となる。 まずは身の回りの日常的なデータやログを何とかしたい。ただ、日常のデータを視覚化するのに数十行以上のコードは書きたくない。まるで息をするかのごとく自然に視覚化を行いたいのだ。そのためには1～2行、長くて数行で済ませることが必要だ。そこでPythonとmatplotlibを使う。加えて、IPythonがあればなお良い。IPythonの導入については以前のブログ記事である IPythonの埋め込みプロットが素晴らしい を参考にして欲しい。 まずは事前にnumpyとmatplotlibをインポートしておく。できればscipyも。 >>> from numpy import * >>> from pylab import * 短いコードで視覚化を行うためには、Pythonの内包表記は必須だ。例えば、5, 2, 1, 5, 8をデータとするグラフを書きたいのならIPythonを使って以下の1行で実現できる。 >>> plot([5, 2, 1, 5, 8]) 数値が行ごとにinput.txtというファイルに書かれていた場合は以下の通り。 >>> plot([int(x) for x in file("input.txt")]) map関数を使えばもっとスマートに書ける。ファイル内の数値を文字列として配列で読み込み、それらの文字列をmap関数によりintで整数に変換する。 >>> plot(map(int, file("input.txt"))) さて、ログが2次元で書かれていた場合はどうするのか。例えば以下のデータがinput.txtに書かれていたとする。 2, 2.5 5, 6.2 6, 3.6 7, 6.3 10, 1.9 この場合、以下のようにすればプロットできる。ファイルから行ごとの文字列を読み出して、それを","を区切りとしてリス...

Pythonでは timeitモジュール を使って簡単に実行時間を計測できる。以下に示すコードはPythonでは一般的なコードだと思う。 たらい回し関数(竹内関数) と階乗を求める関数だ。これを実行した時の時間計測、さらにコードに含まれている関数の実行時間を簡単に測るにはどうすればよいか。 ここでtimeitモジュールが利用できる。まず、Pythonシェル環境では以下の通り。 main関数の測定は次のように行う。stmtで時間計測したい関数を指定して、setupで最初の1回だけ実行する文を指定する。numberは実行する回数となっている。正確を期するなら複数回を指定するべきだろう。 >>> import timeit >>> timeit.timeit(stmt='test_timeit.main()', setup='import test_timeit', number=1) 12 3628800 2.663659573618423 たらい回し関数(tarai)のみの測定。 >>> timeit.timeit(stmt='test_timeit.tarai(12, 6, 0)', setup='import test_timeit', number=1) 2.6390463109480637 階乗関数(factorial)のみの測定。100万回実行。 >>> timeit.timeit(stmt='test_timeit.factorial(10)', setup='import test_timeit', number=1000000) 2.3606330638673825 さらに、コマンドラインでの計測も可能だ。 main関数の測定。コマンドオプションの-sは最初に1回だけ実行する文、-nは実行する文の回数、-rはタイマのリピート数になっている。 $ python -m timeit -n 1 -r 1 -s "import test_timeit" "test_timeit.main()" 12 362880...

あけましておめでとうございます。 新年を迎えて、ふと、今年の西暦である2013を素因数分解したらどんな数に分解されるのか気になったので考えてみた。桁をすべて足し合わせると 2+0+1+3=6 と3の倍数になり、3で割り切れることは明白だ。3で割ると671となる。671に対し桁を一つ飛ばしにして足し合わせた数の差が (6+1)-7=0 で11の倍数(0を含む)なので11で割り切れることも簡単にわかる。671を11で割ると61の素数となる。つまり、2013の素因数分解は 3×11×61 となる。 大きな素数同士による合成数の素因数分解は非常に困難であることが知られている。この性質を利用して多くの暗号アルゴリズムで大きな素数による合成数が利用されている。現在のところ、素因数分解アルゴリズムとしては、楕円曲線法(ECM; Elliptic Curve Method)や複数多項式二次ふるい法(MPQS; Multiple Polynomial Quadratic Sieve)がよく使われているらしい。で、手軽にこれらを利用できるライブラリがないかと軽く調べたところ NZMATH(ニジマス) という数論のためのPythonモジュールがあることを知ったので、早速インストールして使ってみた。 ところで、大きな素数といえばメルセンヌ素数が有名だが、 マラン・メルセンヌ は、2 n -1 に対してnが257以下のとき、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257のときにのみ素数となると主張した。しかし、一部に間違いがあり、n = 61, 89, 107のときも素数であり、また、n = 67, 257は素数ではなく合成数であった。 そこで、誤って素数としていたn = 67のときの 147573952589676412927 について楕円曲線法(ECM)で解かせると、すぐに 193707721×761838257287 と結果が出力された。 >>> import nzmath.factor.methods as methods >>> methods.factor(147573952589676412927, method="ecm") [(193707721L, 1),...

先日、「 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ 」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは 自己回避歩行(Self-avoiding walk) と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のためにゼロサプレス型二分決定グラフ(ZDD; Zero-Suppressed Binary Decision Diagram)と呼ばれるアルゴリズムを利用することにした。このアルゴリズムを開発したのは北大の 湊先生 で、ZDDによりすべての経路を見つけ出すアルゴリズムとして クヌース先生 のSIMPATHを使った。ZDDについてはクヌース先生も強い関心を持っていて、 The Art of Computer Programming Volume 4, Fascicle 1 (TAOCP 4-1)ではBDD/ZDDの詳細な解説を読むことができる。演習問題の解説だけで書籍の半分を使っていることからしても気合の入れようがわかるだろう。 実際に自分のノートPCでZDDアルゴリズムを使ったコードを走らせたら、ほんの10秒程度で10×10マスの問題を解いてしまった。おねえさんがスパコンで25万年かかった問題をノートPCでたった10秒である。約8千億倍の高速化だ。これだけ劇的に変わるとやっぱり楽しい。そして、アルゴリズムの重要性を再認識させられた。 さて、以下におねえさんが利用したであろう自作の深さ優先探索(DFS)プログラムと高速な解法であるZDDアルゴリズムの両方を載せておく。ZDDについては4つのプログラムを1つのPythonスクリプトで統合している。これは、クヌー...

5年ほど前、このブログで 虚数のテトレーション という記事を書いたことがある。 テトレーション(tetration) とは、自らのべき乗を指定された回数反復する演算のことで、 n a と表現する。 3 5 の場合、5 5 5 = 1.911×10 2185 となる。Pythonの関数で表現すれば以下のようになる。 以前の記事では、 ∞ i が 0.43828+0.36059 i に収束することを見つけたのだが、今回はそれに関連したフラクタルについて紹介したい。 テトレーション n a の a には複素数を指定することができる。このとき、 a = x + yi として、それを複素平面に置く。ここで正の整数 n を大きくしていき、発散と判定された n に対応した色で平面を色分けする。発散しない場合、予め決めておいた n の上限値を使う。これで得られる図を テトレーション・フラクタル(tetration fractal) と呼ぶ。 n (x + yi) = a + bi としたとき、 n +1 (x + yi) = a' + b'i は以下のように計算できる。 Pythonでの実装は ActiveSate Code に Tetration Fractal として載っている。今回はこれを少し修正したコード、C++で書いたコード、更にTBBで並列化したコードを用意して、それらの実行速度のベンチマークを取ってみた。 Python C++ C++ with TBB 258.732秒 16.999秒 0.976秒 ここで、複素平面の領域は(-1.5, 0)-(-0.75, 0.75)であり、最大繰り返し数は256としている。画像の大きさは1,024×1,024とした。実行環境はIntel Xeon X5650の2CPUで、12コア・24スレッドとなっている。 以下に、ソースコードを示す。詳細についてはコードを読んでいただきたい。 Pythonによる実装: % ./tetration.py tetration.png -1.5 0.0 0.75 0.75 1024 1024 C++による実装: % ...

先日、 Tokyo.SciPy #3 に参加して、SciPyの生みの親である Travis Olipant氏のセッション を聞いた。その時に最近の IPython では埋め込みプロットができることを知ったので早速入れてみたところ、これがとてもクールでカッコよかったのでここで紹介したい。 埋め込みプロットはIPythonのバージョン0.11からできるようになっている。ただ、自分が使っているLinux環境では普通に持ってくるとバージョン0.10が入ってしまうので使えない。そこで、IPythonの公式サイトから最新版のバージョン0.12を持ってきて入れてみた。 ただ、埋め込みプロットができるのはターミナル版ではなくQt版のシェルなので、それに関連するライブラリなども一緒に入れなくてはならない。IPythonの起動時に何々のライブラリが足りないとかいろいろと文句を言われるが、足りないものをyumなりapt-getなりソースコードをコンパイルなりして順次入れていけば使えるようになると思う。 あと、IPythonの設定ファイルの構成が0.10から大きく変わった。以前は .ipython/ 内の pythonrc を利用していたのだが、それがなくなって、代わりに .ipython/profile_default/ 内の ipython_config.py と ipython_qtconsole_config.py が使われるようになった。デフォルトの設定ファイルは以下のコマンドで作ることができる。 $ ipython profile create そして、埋め込みプロットを使うためのQt版IPythonの起動コマンドは以下の通り。 $ ipython qtconsole --pylab=inline これでQt版シェルが立ち上がって埋め込みプロットを表示できるようになる。 せっかくなので実際に埋め込みプロットを使ってみる。ここでは自分のお気に入りのマンデルブロ集合をプロットしてみた。因みに、シェル上での複数行のソースコードの編集も改良されたので入力がかなり楽になった。冒頭にスクリーンショットを貼っておく。 rangex = arange(-2.0, 1.0, 0.01) rangey = arange(-1.0, 1.0, 0.01) (X, ...