良いもの。悪いもの。

先日、「 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ 」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは 自己回避歩行(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, ...

最近、HTML5に触れる機会があり、その良さが何となく伝わってきたので、何かしら簡単なコードを書いてみたくなった。そこで、ちっちゃいけどリッチ、というギャップを楽しむためにAndroid端末を使うことにした。具体的には、Android端末を SL4A で ウェブサーバにして 、HTML5をインターフェイスにしたお絵かきBBSをPythonで書いてみた。 BBSでは絵とテキストを扱うことができて、それらはAndroid端末上でSQLiteのデータベースで管理される。利用者の利便を考えて、名前などはクッキーで保存する。3G回線や無線LANなどで接続することを考慮して、IPアドレスも取得できるようにした。また、書き込み時にサーバのAndroid端末が振動して書き込みがあったことを知らせてくれる。因みに、NTTドコモの3G回線で使うためには、グローバルIPが振られるmopera Uなどのサービスが必要で、spモードでは利用できない。 実際に作ってみたプログラムのスクリーンショットを冒頭に入れてみた。必要最低限の機能しかないが、それでも文章と画像を保存できるちゃんとした掲示板だ。草の根BBSのころを考えると隔世の感がある。 以下に今回作成したソースコードを載せておく。こんな短いコードでもちゃんと機能するのが不思議な感じだ。 image_bbs.py # -*- coding: utf-8 -*- import sys,os,cgi,sqlite3,datetime import socket,fcntl from wsgiref.simple_server import make_server import android droid=android.Android() LIMIT=10 # 最大表示記事数. DB_FILE='/sdcard/image_bbs.sqlite' P=8080 con=sqlite3.connect(DB_FILE) cur=con.cursor() cur.execute('CREATE TABLE IF NOT EXISTS bbs (id INTEGER NOT NULL PRIMARY KEY AUTOINCREMENT, user TEXT, datetime TEXT, ima...

今年は2012年です。 bool leap_year(int y) { return !(y%4)^!(y%100)^!(y%400); } そして、 leap_year(2012) が真となるので閏年です。平年と比べて一日増えるわけですが、その一日たりとも無駄にしない充実した一年にしたいと思います。 本年もどうぞ宜しくお願い申し上げます。