“最も簡単に fib を高速化する方法”を Squeak Smalltalk で

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

def fib_i(n)
if n == 1
[1, 1]
else
x1, x0 = fib_i(n-1)
[x1 + x0, x1]
end
end

def fib(n)
fib_i(n)[0]
end

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


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 "