「フィボナッチで各種言語をベンチマーク」をPythonでちょっと掘り下げる。

「フィボナッチで各種言語をベンチマーク」を読んで、予想外にPythonの順位が低かったので。手元の環境はWindows XP SP3/Celeron 1200MHz/512MB RAMのPython 2.7.3、実行2回目以降の時間を以下のコマンドで計測。

rem 「cmd /V:ON」で遅延評価を有効化した状態で以下を実行。
echo !TIME! & C:\Python27\python.exe testx.py & echo !TIME!

まずは掲載されていたスクリプト

def fib(n):
  if n < 2: return n
  return fib(n - 2) + fib(n - 1)

#print(fib(38))
print fib(38)

Python 2.xの人なのでprintは文にしました、あとインデントはスペース2個に。

計測1回目1分27秒、計測2回目1分26秒。CPUが100％で張り付く感じ。

lambdaで書き直してみる

fib = lambda n : n>=2 and fib(n-2) + fib(n-1) or n

print fib(38)

計測1回目1分29秒、計測2回目1分29秒。若干遅くなった。。。

再帰しなければ

def fib(n):
  #return reduce(lambda x,y: x+[x[-1]+x[-2],], xrange(n-1), [0,1])[-1]
  # nが0と1の時でもちゃんと動くように変更
  return reduce(lambda x,y: x+[x[-1]+x[-2],], xrange(n-1), [0,1])[n]

print fib(38)

計測1回目0.2秒、計測2回目0.2秒。信じられんくらい速くなった。。。

結論

やっぱしFAQにある通り関数の呼び出しコストは高し、reduceとかlist演算とか組み込みの機能を使えということでした。