たらいまわし関数
いまさらかもしれないが、関数型言語勉強会で、たらいまわし関数についてやってたので、Pythonでどうにかしてみた。
というのも、現場でPythonを使った回答がうまく出来なかった為、リベンジしようという話。
Haskell のたらいまわしtmaeda 日記
C++でたらいまわしドレッシングのような
C#でたらいまわし(hatena (diary ’Nobuhisa))
参考リンクたち。
それぞれの特性をまず考察。
Haskell のたらいまわしは、間違いなく遅延評価の恩恵。
C++ 版のものは、爆速で驚いたが、結局コンパイル時に計算している為、実際には回答を print していることに。
bool がミソで、メモ化しているということらしい。(教えて下さった方sumim’s smalltalking-tos
ご本人に言わせれば、遅延評価は内部的にメモ化に近いことをしているので、厳密に処理系実装の速度比較としては有用ではないとのこと)
C# 版で見てみると、通常版とクロージャによる実装の2通りがある。
# 基本的なたらい回し def tarai(x, y, z): if x <= y: return y return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)) if __name__ == "__main__": print(tarai(20,10,5)) raw_input()
正直、実行速度に耐えないw
C# 版のクロージャ実装をみるとき、LazyInt なるものを宣言している。引数に関数を渡す為の工夫ということか。
ならばクロージャ実装!
# クロージャ的? def tarai(x, y, z): if x <= y: return y z_lazy = z() return tarai(tarai(x - 1, y, lambda : z_lazy), tarai(y - 1, z_lazy, lambda : x), lambda : tarai(z_lazy - 1, x, lambda : y)) if __name__ == "__main__": print(tarai(20,10,lambda : 5)) raw_input()
z_lazy = z()
するまで、z の値は評価しない、で、lambda でとにかく計算するべき処理をスタックに積んでしまうと。
やってみるとわかるけど爆速。でも「lambda : 5」はどうにかならんか(−−;
で、メモ化について考えてみる。
メモ化は、関数に渡された引数パターンを記録して、同じ引数パターンの場合は計算しないと。
そうすることで、異常に深くなる関数スタックの輪を断ち切るとか、、、、。
# メモとってみる memo_dic = {} def tarai(x, y, z): global memo_dic pat = (x, y, z) if not pat in memo_dic: if x <= y: memo_dic[pat] = y else: memo_dic[pat] = tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)) return memo_dic[pat] if __name__ == "__main__": print(tarai(20,10,5)) raw_input()
「pat」で引数パターンを作成して、それをキーに辞書登録。
こうして必要以上の処理をしないっと。
しかし、、、もっとエレガントな書き方できないんだろーか、、、考察の余地アリ。