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

2010/09/10

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

どうしてこれで速くなるの？

最も簡単に fib を高速化する方法 - ドレッシングのような

二つ値を返せば良いんですよ。メモ化なんてしなくていい。

取りあえず Scheme の多値でやってみました。速い。。どうして？

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

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

vallog: PAIP: メモ化, memo, memoize, define-memo

遅延ストリーム。

vallog: fib, tail-call-fib, lazy-fib

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

vallog: fib, tail-call-fib, lazy-fib

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

fib-i なぞ・・・。

追記

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