二つ値を返せば良いんですよ。メモ化なんてしなくていい。
def fib_i(n)最も簡単に fib を高速化する方法 - ドレッシングのような
if n == 1
[1, 1]
else
x1, x0 = fib_i(n-1)
[x1 + x0, x1]
end
enddef fib(n)
fib_i(n)[0]
end
Squeak Smalltalk でも試してみました。ブロックの再帰を使っているので Squeak4.1 が必要です。
| mrknFib | mrknFib := nil. mrknFib := [:n | | pairFib | pairFib := nil. pairFib := [:k | k < 2 ifTrue: [#(1 0)] ifFalse: [ | prev | prev := pairFib value: k-1. prev reversed at: 1 incrementBy: prev first; yourself]]. (pairFib value: n) first]. [mrknFib value: 1000] timeToRun "=> 2 ms "
確かに速い。
ついでに、キャッシュする再帰版とループ版も。
| cache cacheFib | cache := Dictionary new. cacheFib := nil. cacheFib := [:n | cache at: n ifAbsentPut: [n < 3 ifTrue: [1] ifFalse: [ (cacheFib value: n-2) + (cacheFib value: n-1)]]]. [cacheFib value: 1000] timeToRun "=> 6 ms "
| loopFib | loopFib := [:n | | a b | a := 0. b := 1. n-1 timesRepeat: [a := b flag: (b := a+b)]. b]. [loopFib value: 1000] timeToRun "=> 1 ms "