2010/09/10

「最も簡単に fib を高速化する方法」を試してみた。

どうしてこれで速くなるの?
二つ値を返せば良いんですよ。メモ化なんてしなくていい。
取りあえず Scheme の多値でやってみました。速い。。どうして?



あとはまぁ、取りあえず参考までに。

メモ化。昨日のメモ化マクロを使ってみました。


遅延ストリーム。


末尾再帰。ようはループですわな。


普通の再帰。これは 10000 なんてとても試す気になれませんね。。


fib-i なぞ・・・。

追記

わかりました!というか教えて頂きました。末尾再帰の例と同じような計算の仕方だからですね。
末尾再帰ではないし、末尾再帰のようにその都度計算を行うのではなく再帰を戻りながら最後にまとめて計算する点は違えども、計算量は末尾再帰の例と同じということですよね。
というか、末尾再帰とか多値とかそういう話じゃないわけですね。。なんか、すいません。

ありがとうございました!

追記2

爆速過ぎワロタ



実用 Common Lisp (IT Architects’Archive CLASSIC MODER)

0 件のコメント:

コメントを投稿