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

というわけで
ここ
フィボナッチ数列に関する2つのアルゴリズムの速度比較のRubyとPythonでの比較@Python, Ruby - CanI’s Diary
で2つしか比較してなかった奴を
これ
仕方がないのでmatrix.rbを一部移植したよ!@Python (修正:3/17 16:36) - CanI’s Diary
を使って、3つ比較してみました。
一応、ソースをば。

@Python Source

#!/usr/bin/env python

import matrix
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 fib_log(n) :
  return (matrix.Matrix([[1,1],[1,0]])**n)[0,1]

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)
for n in [1000,3000,10000,30000,100000,300000] :
  start = time.time()
  f = fib_log(n)
  _time = time.time() - start
  print "fib_log(%d) == %s; %f secs" % (n, omit_bignum(f,20), _time)

Result

@Ruby

fib_recursive(26) == 121393; 0.551 secs
fib_recursive(27) == 196418; 0.857 secs
fib_recursive(28) == 317811; 1.33 secs
fib_recursive(29) == 514229; 2.147 secs
fib_linear(20000) == 25311623237323612422.{4160}; 0.104 secs
fib_linear(40000) == 14326001654578073438.{8340}; 0.21 secs
fib_linear(60000) == 81083035047844154209.{12519}; 0.391 secs
fib_linear(80000) == 45891789845416942428.{16699}; 0.632 secs
fib_linear(100000) == 25974069347221724166.{20879}; 0.932 secs
fib_log(1000) == 43466557686937456435.{189}; 0.002 secs
fib_log(3000) == 41061588630797126033.{607}; 0.002 secs
fib_log(10000) == 33644764876431783266.{2070}; 0.004 secs
fib_log(30000) == 19042435673462438748.{6250}; 0.029 secs
fib_log(100000) == 25974069347221724166.{20879}; 0.279 secs
fib_log(300000) == 87617325329163457942.{62676}; 2.404 secs

@Python

fib_recursive(26) == 121393; 0.179000 secs
fib_recursive(27) == 196418; 0.289000 secs
fib_recursive(28) == 317811; 0.489000 secs
fib_recursive(29) == 514229; 0.796000 secs
fib_linear(20000) == 25311623237323612422.{4160}; 0.051000 secs
fib_linear(40000) == 14326001654578073438.{8340}; 0.178000 secs
fib_linear(60000) == 81083035047844154209.{12519}; 0.380000 secs
fib_linear(80000) == 45891789845416942428.{16699}; 0.640000 secs
fib_linear(100000) == 25974069347221724166.{20879}; 0.998000 secs
fib_log(1000) == 43466557686937456435.{189}; 0.001000 secs
fib_log(3000) == 41061588630797126033.{607}; 0.002000 secs
fib_log(10000) == 33644764876431783266.{2070}; 0.003000 secs
fib_log(30000) == 19042435673462438748.{6250}; 0.015000 secs
fib_log(100000) == 25974069347221724166.{20879}; 0.082000 secs
fib_log(300000) == 87617325329163457942.{62676}; 0.449000 secs

まとめ

やっぱ、Python早いですねー。
fib_log(任意の行列の冪乗)でも、かなりのスピードを誇っています。
fib_log(300000)とか約6分の1かな。


やっと、fib_log求めるという宿題から解放されました(ぁ