デコレータのクライアントコードについて
Yuya Takeyama
皆様、本日は講習会お疲れさまでした！
Python は未経験で、今回の講習会に向けて 3 日ほど予習していただけですが、
オブジェクト指向なだけでなく、関数型プログラミングにも特化していて、
大変魅力的な言語だと思いました。
さて、本日の講習会の中で出てきた「デコレータ」を自分でもやってみようと、
講習中に以下のようなものを作ろうとしていました。
・関数を生成するデコレータ
・ある引数に大して、常に同一の値を返す
・処理にコストがかかるものも、辞書にキャッシュする
桑田さんのコードを参考になんとか完成させることができました。
ところが、「何がよくなかったのか」がよく分かりません。
言語仕様に起因する部分だとは思いますが・・・。
以下、順を追って説明します。
なかなか上手くいかなかったので、「デコレータによる実装は可能なのか」と
桑田さんに質問したところ、その場で書いていただけました。
■以下は桑田さんのコードです
def fib(x):
return 1 if x <= 2 else fib(x-1)+fib(x-2)
def memoize(f):
memo = {}
def g(x):
if x in memo:
return memo[x]
else:
memo[x] = f(x)
return memo[x]
return g
fib = memoize(fib)
for i in xrange(0, 30):
print i, fib(i)
これは見事に動作しました！
時間の関係上、一度もテストできずに帰宅したのですが、一発で動きました。
return が重複していたりと、記述上の改善点もありますが、
あの短時間に、アドリブでここまで書けるものかと、感動しました。
■そして以下は、改善前の私のコードです。
def fibonacci(n):
return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)
def memorizer(func):
def _func(arg, memo = {}):
if arg not in memo:
memo[arg] = func(arg)
return memo[arg]
return _func
memorized_fibonacci = memorizer(fibonacci)
for i in xrange(0, 30):
print i, memorized_fibonacci(i)
これは、一応の動作はするのですが、肝心のメモ化がなされておらず、
引数が 20 を越える辺りから、処理時間が跳ね上がります。
再帰による処理が数百回行われるため、毎回の処理にコストがかかるのです。
■そして、以下は改善後です。
# memorized_fibonacci = memorizer(fibonacci)
fibonacci = memorizer(fibonacci)
for i in xrange(0, 30):
# print i, memorized_fibonacci(i)
print i, fibonacci(i)
桑田さんのコードと比較したところ、関数の定義はほぼ変わらなかったのですが、
クライアントコードに問題があったようです。
しかし、何故これで動作に違いが出るのかわかりません。
「デコレータ」という名前からすると、元の関数を装飾してあげる改善後の方が、
確かに「それらしい感じ」はしますが、何故改善前では上手くいかないのでしょ
うか。
私自身でも調べているところですが、どなたか教えていただければ幸いです。
よろしくお願いします。
Yuya Takeyama
Makoto Kuwata
お疲れさまです。桑田です。
2010/1/25 Yuya Takeyama <sign.of.the.w...@gmail.com>:
> しかし、何故これで動作に違いが出るのかわかりません。
> 「デコレータ」という名前からすると、元の関数を装飾してあげる改善後の方が、
> 確かに「それらしい感じ」はしますが、何故改善前では上手くいかないのでしょ
> うか。
こういうときは、print文を入れてデータを表示させることで、動作を調べてみましょう。
＃なお全角空白でインデントしているので注意してください。
def memorizer(func):
def _func(arg, memo = {}):
print "*** (debug) memo: ", memo ## ←追加
if arg not in memo:
memo[arg] = func(arg)
return memo[arg]
return _func
これを実行すると、print文が一回しか実行されないことがわかります。
・ ・ ・
で、答えを言っちゃうと、これ↓が原因です。
> memorized_fibonacci = memorizer(fibonacci)
ここで fibonacci をメモ化したのを memorized_fibonacci という別名にしているのが原因です。
つまり memorized_fibonacci はメモ化されてますが、fibonacci はメモ化されてないままです。
そのため、
> def fibonacci(n):
> return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)
は相変わらずメモ化されてない関数 (fibonacci) を呼び出し続けます。
改善後のコードは
> fibonacci = memorizer(fibonacci)
となっており fibonacci がメモ化されるため、お望み通りの挙動になります。
＃スクリーンの片付けありがとうございました。
--
regards,
makoto kuwata
2010/1/25 Yuya Takeyama <sign.of.the.w...@gmail.com>:
makoto kuwata
On 1月25日, 午前12:53, Yuya Takeyama
<sign.of.the.wolf.pentag...@gmail.com> wrote:
> ■以下は桑田さんのコードです
もとのバージョンは、受け取る関数が「引数ひとつ」という制限がありましたが
これを任意個の引数をサポートするように改良してみました。
講習会で説明した内容のよい復習になると思います。
なお全角空白でインデントしているので、試すときは半角空白に直してください。
def memoize(f): # 引数も戻り値も関数であるような高階関数 (資料p.169)
memo = {}
def g(*args): # 可変長引数 (資料p.93)
if args not in memo: # not inはメンバシップ演算子 (資料p.38)
memo[args] = f(*args) # argsはタプルなので辞書のキーに指定できる (資料p.54)
return memo[args]
return g # gは外側のローカル変数であるfとmemoを参照しているので、クロージャ (資料p.177)
@memoize # デコレータ (資料p.182)
def fib(x):
return 1 if x <= 2 else fib(x-1)+fib(x-2) # 三項演算子 (p.43)
#実行例:
# >>> fib(100)
# 354224848179261915075L # 一瞬で答えがでる！メモ化すげー！
@memoize
def tak(x, y, z): # 3つの引数をとる竹内関数でもメモ化可能
if x <= y:
return y
else:
return tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y))
#実行例:
# >>> tak(13, 5, 0)
# 13
なおメモ化の英単語は「memoize」であって「memorize」ではないです。
＃間違えやすいよね。
--
regards,
makoto kuwata
On 1月25日, 午前12:53, Yuya Takeyama
Yuya Takeyama
桑田さん、ご返答ありがとうございます！
> ここで fibonacci をメモ化したのを memorized_fibonacci という別名にしているのが原因です。
> つまり memorized_fibonacci はメモ化されてますが、fibonacci はメモ化されてないままです。
>
なるほどー、と言いたいところですが、飲み込むのにもう少し時間がかかりそう
です。
おっしゃっていることは何となくわかるのですが、実際に書いて検証してみます。
可変引数バージョンについては、昨日の講習会でも興味深かったので、
作ってみようと思っているところでした！
勉強になります。
> なおメモ化の英単語は「memoize」であって「memorize」ではないです。
> ＃間違えやすいよね。
何から何まで恐れ入りますw
プログラムを書く以上、言葉に正確でなくてはいけませんね。
Yuya Takeyama
Yuya Takeyama
Python の print 文は便利ですね！
桑田さんのデバッグコードを今朝動かしてみたのですが、
すぐにわかりました。
というか、今思えば現員が単純過ぎてお恥ずかしいぐらいですw
関数が、自分自身を参照できるエイリアスを持って入れば、
代入先の変数名が違っていてもいけそうですね。
Yuya Takeyama
(2010年01月25日 13:13), makoto kuwata wrote: