Categories

  • Android開発
    android marketで目指せ億万長者(ウソ)
  • cocos2d
    pythonでも使えるゲームフレームワーク
  • Google
    ここには未来を開くためのAPIがたくさん用意されている。
  • GoogleAppEngine
    どこまでもスケールアウトするクラウドサービス。使いこなすのが大変
  • Hack
    様々な電子機器を本来の用途とは別の用途に使ってみる。
  • iPhone開発
    app storeで目指せ億万長者(ウソ)
  • python
    LightWeightLanguageで一番難しいがLispにも通じるところがある面白い言語。
  • TIPS
    覚えておくともしかしたら役に立つかもしれないチョットしたこと。
  • うまくいきません
    やってみたけど、うまくいかなかった失敗記事
  • ネット世界
  • 夢見るソフトウェア
    こんなのいいな、できたらいいな、いつかつくろう
  • 開発環境
    開発するまえに環境を整えた記録、次に同じことをするためめの忘備録
無料ブログはココログ
My Photo

« July 2011 | Main | October 2011 »

September 12, 2011

PyPyは素晴らしい

pythonのコンパイPyPyをGoogle Dev Quizに挑戦中に知った。

何か素晴らしい響きなので、macで試してみた。

PyPyのページからmac用64bit版をダウンロードした。
ダウンロードページ

 ファイルを展開して、Downloadsから適当な場所にコピーする。
といっても何が適切なのかわからないので、ホームディレクトリにおいた

でもって、/usr/local/bin のディレクトリにpypyをシンボリックリンクする。
コピーじゃなくてシンボリックリンクだ。
sudo ln -s /Users/ohsaruman/pypy-1.6/bin/pypy pypy

あとは、pythonのかわりにpypyとタイプするだけ。

ベンチマーク替わりに、スライドパズルの課題でちょっと難しいものをやってみた。
ノーマルのpythonでは10分かかるが、pypyでは2分。大好きだPyPy

time python google-pazzle.py google.txt

real 10m32.328s
user 9m43.628s
sys 0m6.940s


time pypy google-pazzle.py google.txt

real 2m1.954s
user 1m56.695s
sys 0m2.553s

DevQuizに挑戦してみた

 今年のGoogle developer day のQuizはスライドパズルだった。
昔からある15個の数字が書いてあるコマを動かして順番に揃えるアレ、遠足の時にぼっちになったら黙々とやっていたトラウマとかどうでもいい。

普通のパズルと違って、制約事項が2つある。
1.盤面に動かせないコマがある。
2.上下左右に動かせる数は上限がある。上限を超えると失格
問題の数は5000問で1問解くごとに0.01点が与えられる。

1の条件により、一般的な15パズル解法プログラムは使えない。
また、上限があるということは、手数は丁度もしくは足りないため、正解数が最大になる組み合わせを探すことになるだろうと予測した。
これにより、満点ということはなく4900問前後での闘いになるだろうと読んだ。まあ、結果的には予測は大外れだったわけだが。

言語は日頃使っていないpythonを選択。数値演算が得意そうだし、googleに提出するしね。

 作戦は「空」つまり0を上下左右に動かして結果を記録して1手、次に1手で記録した盤面を全て上下左右を調べて記録、これで2手。
pythonのmapを使い、インデックスを盤面とした。検索が超早い。
 が、しかし爆発的に記憶する盤面の数が増えていく。当然、メモリが足りない。そこで、各コマについて本来の位置との距離を求め、合計が大きなものすなわち正解から遠いものを捨てた。
また、結果から逆に問題の方向へ動かすこともやった。
最大手数を100手あたりに設定して、3000問は解けた。手数が多いと何をやってもメモリ不足となる。

9月に入って結果を見ると全問正解者がいらっしゃいます。え~、目論見が外れた。

締め切り前日になって、盤面の大きなパズルは半分ずつとけばいいと気がついた。
急いで実装してみたが、半分でもまだ手数が多すぎる、じゃあ1/4とか1/16でということになるが、時すでに遅し。

計算時間を短くするために、複数のマシンで分散して処理できるようにした。8台で分散させたが、COREi7のマシン1台に負けるんだよね。

満点にはならなかったけど、pythonはプログラムしていて楽しい。他の言語に比べて、コアな部分に専念できるような感じた。
Cythonやpypyは今回試していないが、こういうものがあると知っただけでも今回参加したかいがあった。

以下ソース。ちょっと汚い。

Continue reading "DevQuizに挑戦してみた" »

« July 2011 | Main | October 2011 »