RE:自分ならこう書く - pythonでA*
おぉぉぉ、コードが添削されとる！
しかし、ソート付きキューのheapqは知らなかったです、勉強になります。
それにしても、C言語のベタ移植だったとはいえ、Pythonに直すと短くなるもんだなぁ！！
・・・でも、短くしすぎでは？ (;・_・）
重要な処理まではしょっている気が・・・
これ、斜め移動を可能にする場合、nexts()とdistance()をいじると思うんですが
def nexts(pos): wall = "O" if dungeon[pos[0] - 1][pos[1]] != wall: yield (pos[0] - 1, pos[1]) if dungeon[pos[0] + 1][pos[1]] != wall: yield (pos[0] + 1, pos[1]) if dungeon[pos[0]][pos[1] - 1] != wall: yield (pos[0], pos[1] - 1) if dungeon[pos[0]][pos[1] + 1] != wall: yield (pos[0], pos[1] + 1) if dungeon[pos[0]-1][pos[1]-1] != wall: yield (pos[0]-1, pos[1]-1) if dungeon[pos[0]+1][pos[1]-1] != wall: yield (pos[0]+1, pos[1]-1) if dungeon[pos[0]-1][pos[1]+1] != wall: yield (pos[0]-1, pos[1]+1) if dungeon[pos[0]+1][pos[1]+1] != wall: yield (pos[0]+1, pos[1]+1) pass def distance(path): px,py = path[0] dist = 0. for (nx,ny) in path[1:]: dist += ((px - nx)**2 + (py - ny)**2) ** 0.5 #dist += 1.41421356237 if (px-nx)!=0 and (py-ny)!=0 else 1.0 px,py = nx,ny return dist
として、経路計算をすると・・・
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO Os* O O O O ***** O O *O O O O O **** O *OOOO gO O * O O O *OOOO* O *O OOOO OO*OOOOOOOOOOOOOOO *O *O *O** O O ********* O *O *O * * O O OOO* O *O *OOOOOOOOO* O O OO O *OOOO* O *O *** OO* O O O O **** O *O* O * O* O O OOO O O * O *O* O O O O O * O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
よーーーーーくみると、2箇所ほど遠回りしてます。
で、原因はですね、なんとなくは分かるんですけど、特定には至ってません、すみません。
distance()の計算でしくじってるのかなぁ？なんか気持ち悪いなぁ・・・
孫トラックバック
勝手に採点 (Re: 自分ならこう書く - pythonでA*) - methaneのブログ
setの話 - Doge log
* checked が配列なので pos in checked が遅い。
直したらこんな感じ。
def astar(init, goal, nexts, distance=len, heuristic=lambda pos: 0): import heapq hpush = heapq.heappush hpop = heapq.heappop queue = [] checked = set([init]) hpush(queue, (distance([init]) + heuristic(init), [init])) while queue: score, path = hpop(queue) last = path[-1] if last == goal: return path for pos in nexts(last): if pos in checked: continue checked.add(pos) newpath = path + [pos] hpush(queue, (distance(newpath) + heuristic(pos), newpath))大きい問題なら結構差がつくかも。特に checked がモロに計算量に影響するので。
勝手に採点 (Re: 自分ならこう書く - pythonでA*) - methaneのブログ
なるほど、確かにsetを使うと速くなりますね。
結果
9.95783400536 0.000999927520752setの話 - Doge log
って、set速えぇな！！
まぁ、線形探索(list)と2分木の探索(set&dict)ですから、速度に差がつくのは当たり前なんですが、結構差がつくんだなぁ。
よく使うファイル操作早引き
Pythonでよく使う便利なファイル操作のまとめ。
こういう便利な機能を使っちゃうと、C言語でツールを作るのがバカらしくなりますね。
テンポラリファイル（一時ファイル）
tempfileモジュールを使います、テンポラリファイルを作成する方法はいくつかあって、一般的にはTemporaryFile()かmkstemp()を使うと思います。
TemporaryFile()は、ファイルハンドルをクローズすると自動的にファイルが削除されます。
ファイルに同時アクセスが可能かはOS依存です、ファイルをぶろWindowsとかだと意外と使いにくいです。
import tempfile fh = tempfile.TemporaryFile() fh.write("test write.") fh.close()
一方、mkstemp()はファイルハンドルをクローズしてもファイルが存在します、しかし、ユーザーの責任でファイルを削除する必要があります。
import tempfile import os tmp_file = tempfile.mkstemp() #mkstemp()の戻り値は、ファイル値とファイルの絶対パス print tmp_file #ファイル値はfdopen()で扱う fh = os.fdopen(tmp_file[0], "w") fh.write("test write.") fh.close() #mkstemp()の場合、ユーザーが責任を持ってファイルを削除 os.remove(tmp_file[1])
ファイル同士の比較
filecmpモジュールを使えば、ファイルの比較は1行でOK。
ファイルの中身まで調べて比較してくれます。
import filecmp filecmp.cmp(’test.txt', 'test.txt') #=> True filecmp.cmp(’test.txt', 'readme.txt') #=> False
ディレクトリの比較はfilecmpモジュール配下のdircmpクラスを使います。
import filecmp obj = filecmp.dircmp('dir1','dir2') #比較結果をstdoutに出力 obj.report() #dir1だけにあるファイルおよびサブディレクトリのリスト print obj.left_only #dir2だけにあるファイルおよびサブディレクトリのリスト print obj.right_only #両方のディレクトリにあるサブディレクトリのリスト print obj.common_dirs #両方のディレクトリにあるファイルのリスト print obj.common_files #両方のディレクトリにあり、一致するファイルリスト print obj.same_files #両方のディレクトリにあり、一致しないファイルリスト print obj.diff_files
高レベルなファイル操作
shutilモジュールでデレクトリを再帰的にコピー＆削除＆移動をしてくれます。
import shutil #ディレクトリを再帰的にコピー shutil.copytree("src_dir", "dst_dir") #ディレクトリを再帰的に削除 shutil.rmtree("src_dir") #ディレクトリを再帰的に移動 shutil.move("src_dir", "dst_dir")
ファイルリストをワイルドカードでフィルタリング
fnmatchモジュールで、ファイルリストをフィルタリングすることができます。
import fnmatch a = ["test.txt","test.py","test.png","foo.txt"] #ファイルリストをフィルタリング fnmatch.filter(a,"*.txt") #=>['test.txt', 'foo.txt'] #単一のファイルを判断 fnmatch.fnmatch("test.txt", "*.txt") #=>True #大文字、小文字を判断する場合はfnmatchcase fnmatch.fnmatchcase("test.TXT", "*.txt") #=>False
wxMaxima覚書
wxMaximaとは？
「wxMaxima」とは、フリーの数式処理ソフト「Maxima」のGUIフロント版です。
以下のページからwxMaximaをダウンロードすることができます。
http://wxmaxima.sourceforge.net/wiki/index.php/Main_Page
Ubuntu(Linux)の場合は、以下のコマンドを打つだけでインストールできます。
sudo apt-get install wxmaxima
wxMaximaの使い方
wxMaximaを立ち上げると、こんな感じのウインドウが立ち上がります。
「INPUT:」と書いてあるボックスに数式を代入してEnterキーを押せばOKです。Windows版など、バージョンによってはCtrl+Enterキーを押す場合もありますので注意が必要です。
(%i) 1+2-3; (%o) 0 (%i) 1/3; (%o) 1/3 (%i) 1/3 + 2/4 + 3/5; (%o) 43/30
1/3が「0.333...」という実数ではなく、「1/3」という有理数として扱います、このため計算誤差が非常に少なくなっています。
有理数を実数(float)に変換したい場合は「float()」、floatよりも精度が必要な場合は「bfloat()」を使います。
(%i) float(1/3); (%o) 0.33333333333333 (%i) 1/3 + 2/4 + 3/5; (%o) 43/30 (%i) bfloat(%); (%o) 1.433333333333333b0
ちなみに%は、1つ前の出力値を表します。
他にもべき乗は「^」または「**」、階乗計算は「!」で表します。
(%i) 2**3; (%o) 8 (%i) 5!; (%o) 120
変数と関数の定義
変数は「:」、関数は「:=」で設定します。
(%i) t: 4; (%o) 4 (%i) t*5; (%o) 20 (%i) sig(n):= n*(n+1)/2; (%i) sig(10); (%o) 55
式の簡略化
式の簡略化をする場合は「ratsimp()」を使います。
自動で通分や余分な計算を省略してくれるので、非常に便利です。
(%i) (A-B)*C + B**2 + (-B-A)*C + B**2; (%i) ratsimp(%); (%o) 2*B**2-2*B*C
方程式を解く
方程式を解くには「solve()」を使います。
下の例では、方程式「0=(A-B)*D + C**2 + (-B-A)*C+B**2」をAについて求めた場合です。
(%i) (A-B)*D + C**2 + (-B-A)*C+B**2; (%i) solve([%], [A]); (%o) [A=(B*D-C^2+B*C-B^2)/(D-C)]
微分・積分
微分は「diff()」、積分は「integrate()」を使います。
微分積分はよく使うので助かります。
(%i) integrate(x^2, x); (%o) x^3/3 (%i) diff(sin(x),x); (%o) cos(x)
順列・組み合わせ
順列・組み合わせを使うにはfunctsモジュールをロードする必要があります。
順列は「permutation(m,n)」、組み合わせは「combination(m,n)」を使います。
(%i) load(functs); (%i) combination(5,3); (%o) 10 (%i) permutation(10,4); (%o) 5040
今更ながらjsonを使いました
Python2.6になって、jsonが標準モジュールになりましたね。
JavaScriptとの連携をするつもりはないんですが、可読性のあるpickleとして使えるかなと思いました。
import json a = { "name":"Tim", "age":19, "email":"tim@timcity.com", "visible":True } json.dump(a, open('output.json','w'))
■output.json
{"visible": true, "age": 19, "name": "Tim", "email": "tim@timcity.com"}ちゃんとファイルに出力されましたね。
（よくサンプルで見かけるjson.dumps()は、ファイルではなく文字列に出力します）
でも長い1行で出力されてるため、可読性に問題ありですよね。
複数行に分割しインデントを付けて欲しい場合は、indent引数にインデント数を指定します。
辞書キーをソートしてほしい場合は、sort_keys引数にTrueを指定します。
標準では「:」と「,」の区切り文字の後ろに空白が挿入されています、separators引数で空白も削除する事ができます。
import json a = { "name":"Tim", "age":19, "email":"tim@timcity.com", "visible":True } json.dump(a, open('output.json','w'), indent=2, separators=(',',':'), sort_keys=True )
■output.json
{
"age":19,
"email":"tim@timcity.com",
"name":"tim",
"visible":true
}これで人が読みやすい形になりましたね。
保存したファイルを読みだすコードは以下の通り。
import json a = json.load(open('output.json','r'))
ちなみに独自拡張のエンコードとデコードをしたい場合は、以下のページを参考にしてください（手抜き）
http://gihyo.jp/dev/serial/01/pythonhacks/0011
個人的には、独自拡張のエンコードとデコードを書くくらいなら、pickleを使うかな・・・
どうしてもjsonを使いたいという方には「jsonpickle」というライブラリがあるので、そちらを使った方がいいかも。
クロージャの正しい使い方
すごい乱数生成アルゴリズム「xorshift」
みなさん、こんにちは、今回は乱数の話です。
特に複数機種でのコンシューマ機でゲームを開発をしていると、機種間で乱数値を統一するために乱数生成アルゴリズムを自作しますよね。
そこでよく使われるアルゴリズムが「線形合同法」です、内容は至って簡単で、以下の漸化式を使います。
A,B,Mは定数で、どの値が入るかは処理系依存です。
例えばUnixなどの処理系ではA=1103515245,B=12345,M=2147483647などが入ります。
C言語ですと以下のようになります。
static unsigned int x=1; void srand(unsigned int s) { x=s; } unsigned int rand() { x=x*1103515245UL+12345UL; return x&2147483647UL; }
この「線形合同法」は計算が簡単で高速ですから、いろいろな環境と言語で使われています。
（C言語やJava、C#などの標準乱数は、このアルゴリズムが使われています）
しかし、線形合同法の生成する乱数は品質に非常に問題ありなんです。
周期はどう頑張っても2^32以上は期待できませんし、特に下位ビットの方は周期的な偏りがあり品質が非常に悪い。
最近では下位ビットを捨てて、品質を上げている処理系もあります。
品質を求めるなら「メルセンヌツイスター」でしょうね、(2^219937)-1とほぼ無限とも言える周期で、値もまんべんなく分布しています。
でも、計算時間が少し長いので、リアルタイムゲームではちょっと使いにくいのが玉にキズですね。
（でも最近は改良型のSFMTが出てきて、それも変わりつつあるんですが・・・）
簡単だけどすごいやつ「xorshift」
で、今回紹介するのが「xorshift」です、こいつがスゴイ！
メルセンヌツイスターには及ばないものの、(2^128)-1の周期を持っており値の偏りも少なく、品質が非常に高いのが特徴です。
しかも驚くことに、計算はビットシフトとXORだけでなので非常に高速です。
以下、Pythonでの実装例です。
#coding:utf8 x,y,z,w = (123456789,362436069,521288629,88675123) def seed(s): global x,y,z,w x,y,z,w = s if x+y+z+w <= 0: raise ValueError, "Please do not substitute 0 for seed." def randint(a,b): global x,y,z,w t = (x^(x<<11)) x,y,z = y,z,w w = w=(w^(w>>19))^(t^(t>>8)) return (a+w)%b #乱数のシードは4つの整数値を指定 seed([12345678,4185243,776511,45411]) #乱数生成 for _ in range(100): print randint(0,100)
こんな簡単なコードなのにちゃんと乱数してますね。
計算もXORとシフトだけなので、計算速度は線形合同法と比べても遜色はありません、品質は断然xorshiftが上ですけどね。
xorshiftの論文は、以下のページからPDFファイルをダウンロードできます。（英文）
http://www.jstatsoft.org/v08/i14/
論文にはC言語の実装も書かれていますので、そちらもどうぞ。
unsigned long xor128(){ static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; unsigned long t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); }
あ、ちなみにPythonの標準乱数は、C言語で書かれたメルセンヌツイスターです。なので、Pythonでxorshiftを実装する意味はあんまないです（ならなぜ紹介したっ！）
何が言いたいかといいますと、Python最高！！
