2012年9月15日土曜日

「フカシギの数え方」の問題を解いてみた

このブログ記事をはてなブックマークに追加

先日、「『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(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スクリプトで統合している。これは、クヌース先生のSIMPATHおよびSIMPATH-REDUCEを利用しており、また、SGB (Stanford GraphBase)ライブラリでグラフを作成し、経路の数え上げにGMPを使ったC++で自作コードを組んだためである。最初はSIMPATHを参考に実装して一つのソースコードに統一しようかと思ったが、解説もちゃんと書かれているクヌース先生のコードをそのまま利用することにした。これらのプログラムの簡単な解説と使い方を載せておく。

まずはDFSによる実装を以下に示す。Node構造体から経路を辿って数え上げるだけの単純なプログラムである。


実行方法は以下の通り。引数の7は7×7のノードを表しており、マスで表現すれば6×6マスとなる。そして計算結果として、575,780,564通りの経路が探索されたことを示している。因みに7×7ノード(6×6マス)で約3分ほどの時間が掛かっており、それ以上の大きさだと現実的な時間で解くことが難しくなってくる。

% ./count_lattice_path_dfs 7 Count all paths from (0, 0) to (6, 6) in the 7x7 lattice graph: Count: 575780564

次に、ZDDを利用したプログラムのビルド方法を示す。

ビルドをする前にSGBおよびGMPを準備しておく。また、SIMPATHおよびSIMPATH-REDUCEについてはCWEBを利用しているので、それも入れておく。

最初に、SGBライブラリを用いて格子状のグラフを作成する。

% gcc gen_lattice.c -O3 -lgb -o gen_lattice

ソースコード内でグラフを下記のように作成している。board関数はチェスのような格子状のグラフを作成することができる。他にもグラフを作成する便利な関数が多数あるので、興味のある方はSGBライブラリのgb_basic.wあたりを参照して欲しい。

Graph* g = board(N, M, 0L, 0L, 1L, 0L, 0L);


次に、SIMPATHおよびSIMPATH-REDUCEを以下のようにビルドする。

% wget http://www-cs-faculty.stanford.edu/~uno/programs/simpath.w % ctangle simpath.w % gcc simpath.c -O3 -lgb -o simpath

% wget http://www-cs-faculty.stanford.edu/~uno/programs/simpath-reduce.w % ctangle simpath-reduce.w % gcc simpath-reduce.c -O3 -lgb -o simpath-reduce

因みに、ctangleでC言語への変換、cweaveでTeX形式への変換を行うことができるので、以下のようにTeX形式のドキュメントも一緒に作っておくことをお勧めする。また、これらのアルゴリズムを理解するために前述のTAOCP Vol. 4を読んでおくことが望ましい。

% cweave simpath.w % tex simpath.tex % dvipdf simpath.dvi # PDFファイルが必要なら. % cweave simpath-reduce.w % tex simpath-reduce.tex % dvipdf simpath-reduce.dvi # PDFファイルが必要なら.

最後に、ZDDから経路を数え上げるプログラムをコンパイルする。

% g++ count_path_mp.cpp -O3 -lgmp -o count_path_mp

経路を一つ一つ数えていては高速に数え上げるという点で意味がなくなってしまうので、ちゃんとメモ化再帰で数える。ZDDは高度に圧縮されているのでメモ化再帰でほとんど瞬時に数え上げることができる。


そして、上記のプログラムを統括するPythonスクリプトが以下となる。グルー言語としてもPythonは優秀だ。


実行方法は以下の通り。

% ./count_lattice_path.py 8 Count all paths from (0, 0) to (7, 7) in the 8x8 lattice graph: Count: 789360053252

DFSのプログラム同様、引数の8は8×8ノード(7×7マス)を表している。そして計算結果として、789,360,053,252通りの経路が探索されたことを示している。また、中間ファイルとして以下が出力される。

lattice_08.gb # SGBによるグラフデータ. lattice_08.out # SIMPATHの出力: not-necessarily-reduced BDD lattice_08.out.r # SIMPATH-REDUCEの出力: ZDD lattice_08.out.rc # SIMPATH-REDUCEの出力を再番付. lattice_08.log # 一連の実行ファイルのログ.

因みに、DFSで7×7ノード(6×6マス)を解くと3分ほどかかったが、ZDDでは0.1秒未満で完了した。また、ZDDで14×14ノード(13×13マス)は数分で終わることを確認したが、それ以上は途中で搭載メモリ以上に必要なメモリが大きくなるので実行していない。

続きを読む...

2012年5月14日月曜日

テトレーション・フラクタル

このブログ記事をはてなブックマークに追加

5年ほど前、このブログで虚数のテトレーションという記事を書いたことがある。テトレーション(tetration)とは、自らのべき乗を指定された回数反復する演算のことで、na と表現する。35 の場合、555 = 1.911×102185 となる。Pythonの関数で表現すれば以下のようになる。


以前の記事では、i が 0.43828+0.36059i に収束することを見つけたのだが、今回はそれに関連したフラクタルについて紹介したい。

テトレーション naa には複素数を指定することができる。このとき、a = x + yi として、それを複素平面に置く。ここで正の整数nを大きくしていき、発散と判定されたnに対応した色で平面を色分けする。発散しない場合、予め決めておいたnの上限値を使う。これで得られる図をテトレーション・フラクタル(tetration fractal)と呼ぶ。

n(x + yi)=a + biとしたとき、n+1(x + yi)=a' + b'i は以下のように計算できる。




Pythonでの実装はActiveSate CodeTetration 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++による実装:

% g++ tetration.cpp -o tetration -O3
% ./tetration tetration.out -1.5 0.0 0.75 0.75 1024 1024
% ./image_tetration.py tetration.out tetration.png



TBBを利用したC++による並列化実装:

% g++ tetration_tbb.cpp -o tetration_tbb -ltbb -O3
% ./tetration_tbb tetration.out -1.5 0.0 0.75 0.75 1024 1024
% ./image_tetration.py tetration.out tetration.png



C++の実行ファイルで生成された出力ファイルを画像ファイルに変換するスクリプトを以下に示す。


続きを読む...

2012年3月31日土曜日

IPythonの埋め込みプロットが素晴らしい

このブログ記事をはてなブックマークに追加

先日、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, Y), Z = meshgrid(rangex, rangey), [] for y in rangey: Z_ = [] for x in rangex: c, z = complex(x, y), 0.0 for i in range(100): if abs(z) > 2.0: break z = z * z + c Z_.append(i) Z.append(Z_) contourf(X, Y, Z, arange(100.0))

続きを読む...

2012年2月19日日曜日

Android端末をサーバにしてHTML5を使ったお絵かきBBSを作成する

このブログ記事をはてなブックマークに追加

最近、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, image TEXT, text TEXT)') INSERT_DB='INSERT INTO bbs VALUES(NULL,?,?,?,?)' def ipconfig(): s=socket.socket(socket.AF_INET,socket.SOCK_DGRAM) s.connect(('gmail.com',80)) return s.getsockname()[0] def post(user,image,text): if image=='' or text=='': return if user=='': user='匿名' dt=datetime.datetime.today().strftime('%Y-%m-%d %H:%M:%S') cur.execute(INSERT_DB,(cgi.escape(user.decode('utf-8')),dt,cgi.escape(image.decode('utf-8')).replace('\n','<br />'),cgi.escape(text.decode('utf-8')).replace('\n','<br />'))) con.commit() droid.vibrate() #droid.notify(user,text) def bbs(environ,start_response): global IP if environ['PATH_INFO']=='/': user='' if environ.has_key('HTTP_COOKIE'): cookie={} for d in environ['HTTP_COOKIE'].strip(';').split(';'): d=d.split('=') cookie[d[0]]=d[1] if cookie.has_key('BBSUSER'): user=cookie['BBSUSER'] if environ['REQUEST_METHOD']=='POST': fs=cgi.FieldStorage(fp=environ['wsgi.input'],environ=environ,keep_blank_values=1) user=fs.getfirst('user','').strip() image=fs.getfirst('bbsImage','') text=fs.getfirst('text','').strip() post(user,image,text) data=u"""<!DOCTYPE html> <html><head> <meta http-equiv="Set-Cookie" content="BBSUSER=%s"> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>Image BBS by Android</title></head><body> <p><a href="http://%s:%d">http://%s:%d</a></p> <form action="/" method="post" id="form"> <span>名前:<input type="text" name="user" size="20" maxlength="30" value="%s" /></span> <div><canvas id="bbsCanvas" width="400" height="200" style="border:1px solid;"></canvas></div> <textarea name="text" cols="40" rows="5"></textarea><br /> <input type="hidden" name="bbsImage" id="bbsImage" /> <span><input type="button" onclick="clearCanvas();" value="画像消去" /></span> <span><input type="button" value="更新" onclick="location.reload(true);" /></span> <span><input type="button" value="送信" onclick="setImage();this.form.submit();" /></span> </form> <script type="text/javascript"> var mouseDownFlag = false; window.onload = function() { draw(); setImage(); }; function draw() { var canvas = document.getElementById('bbsCanvas'); if (!canvas || !canvas.getContext) return false; var ctx = canvas.getContext('2d'); canvas.onmousemove = function(e) { if (mouseDownFlag) { var rect = e.target.getBoundingClientRect(); ctx.beginPath(); ctx.arc(e.clientX - rect.left, e.clientY - rect.top, 3, 0, Math.PI * 2, false); ctx.fill(); } } canvas.onmousedown = function(e) { mouseDownFlag = true; } canvas.onmouseup = function(e) { mouseDownFlag = false; } canvas.onmouseout = function(e) { mouseDownFlag = false; } } function setImage() { var canvas = document.getElementById('bbsCanvas'); if (!canvas || !canvas.getContext) return false; document.getElementById("bbsImage").value = canvas.toDataURL(); } function clearCanvas() { var canvas = document.getElementById('bbsCanvas'); if (!canvas || !canvas.getContext) return false; var ctx = canvas.getContext('2d'); ctx.clearRect(0, 0, 400, 200); setImage(); } </script>""" % (user,IP,P,IP,P,user) cur.execute('SELECT * FROM bbs ORDER BY id DESC') for i, row in enumerate(cur): if i>=LIMIT: break data+=('<div><p>%d <b>%s</b> %s</p><img src="%s" alt="Image" width="400" height="200" style="border:1px solid;" /><p>%s</p></div>' % row) data+='</body></html>' start_response('200 OK',[('Content-type','text/html;charset=utf-8')]) return [data.encode('utf-8')] IP=ipconfig() httpd=make_server('',P,bbs) httpd.serve_forever()

続きを読む...

2012年1月1日日曜日

恭賀新年

このブログ記事をはてなブックマークに追加

今年は2012年です。

bool leap_year(int y) { return !(y%4)^!(y%100)^!(y%400); }

そして、leap_year(2012) が真となるので閏年です。平年と比べて一日増えるわけですが、その一日たりとも無駄にしない充実した一年にしたいと思います。

本年もどうぞ宜しくお願い申し上げます。

続きを読む...