読者です 読者をやめる 読者になる 読者になる

フィボナッチ数列に関する2つのアルゴリズムの速度比較のRubyとPythonでの比較@Python, Ruby

おもしろそうだったので。
id:qnighyさんの
フィボナッチ数列に関する3つのアルゴリズムの速度比較@Ruby - 簡潔なQ
を読んで、おもしろそうなので@Pythonでもやってみようと思っていたのですが、記憶の彼方に忘れ去られていました。
ちょうど、暇な時に思い出したので比較でも。
きっと、多倍長計算の速度とか、関数の再帰的に呼び出したときの処理の差がでると思われます。


※fib_log(n)は行列演算で、Matrixクラスとかいう便利クラスはPythonにはないので、numpyとかで計算しようとしました。が、うまくいかなかったので(原因調査中)今回は比較してません。そのうち比較記事あげるつもりです。

環境

@Python Source

#!/usr/bin/env python

import time

def fib_recursive(n) :
  if n == 0 :
    return 0
  elif n == 1 :
    return 1
  else :
    return fib_recursive(n-1)+fib_recursive(n-2)

def fib_linear(n) :
  a, b = 0, 1
  for i in range(n) :
    a, b = b, a+b
  return a

def omit_bignum(n, dig = 20) :
  s = str(n)
  if len(s) <= dig+5 :
    return s
  return s[:dig] + ".{" + str(len(s)-dig) + "}"

for n in [26,27,28,29] :
  start = time.time()
  f = fib_recursive(n)
  _time = time.time() - start
  print "fib_recursive(%d) == %d; %f secs" % (n, f, _time)
for n in [20000,40000,60000,80000,100000] :
  start = time.time()
  f = fib_linear(n)
  _time = time.time() - start
  print "fib_linear(%d) == %s; %f secs" % (n, omit_bignum(f,20), _time)

訳してる途中で

AttributeError: 'float' object has no attribute 'time'

とか言われて一瞬悩んだが、そういえばtimeモジュールimportしてたので、変数timeは_timeにしました。
あとは、逐語訳しただけ。

Result

@Ruby

fib_recursive(26) == 121393; 0.482 secs
fib_recursive(27) == 196418; 0.801 secs
fib_recursive(28) == 317811; 1.325 secs
fib_recursive(29) == 514229; 2.047 secs
fib_linear(20000) == 25311623237323612422.{4160}; 0.073 secs
fib_linear(40000) == 14326001654578073438.{8340}; 0.202 secs
fib_linear(60000) == 81083035047844154209.{12519}; 0.377 secs
fib_linear(80000) == 45891789845416942428.{16699}; 0.606 secs
fib_linear(100000) == 25974069347221724166.{20879}; 0.887 secs

@Python

fib_recursive(26) == 121393; 0.164000 secs
fib_recursive(27) == 196418; 0.269000 secs
fib_recursive(28) == 317811; 0.441000 secs
fib_recursive(29) == 514229; 0.712000 secs
fib_linear(20000) == 25311623237323612422.{4160}; 0.053000 secs
fib_linear(40000) == 14326001654578073438.{8340}; 0.173000 secs
fib_linear(60000) == 81083035047844154209.{12519}; 0.357000 secs
fib_linear(80000) == 45891789845416942428.{16699}; 0.602000 secs
fib_linear(100000) == 25974069347221724166.{20879}; 0.918000 secs

まとめ

fib_recursive(単純再帰)では、@Pythonの方が圧倒的に早いですが、fib_linearでは、ほぼ両者同じタイムです。
このことから

  • 多倍長計算の処理能力の差はほとんど見受けられない
  • 再帰呼び出しでは大きな差がついたよ!

とか言えそうです。
P.S. 今回はRubyのソースを読まなきゃならんので、若干苦しみましたが、google先生に頼って生き延びました。google先生は偉大だよ。うん。
.each do〜endとか気持ち悪かったです。