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

各言語でのフィボナッチ数列に関する3つのアルゴリズムでの速度比較

ベンチマークみたいなあれです。
思えば、過去にいろいろしてきました。
フィボナッチ数列に関する3つのアルゴリズムの速度比較のRubyとPythonでの比較@Python, Ruby - CanI’s Diary
とか。


で、rubyたんが1.9になったとか、pythonが3.0系になったとかいろいろあったので、改めて速度比較をしてみようかなと。
今回は、我らがIronpythonIronrubyにも加わっていただきました。

@Ruby Source

id:qnighyさんの
フィボナッチ数列に関する3つのアルゴリズムの速度比較@Ruby - 簡潔なQ
から。
以下、引用。

#!/usr/bin/ruby -Ku

require 'matrix'

def fib_recursive(n)
  case n
  when 0
    return 0
  when 1
    return 1
  else
    return fib_recursive(n-1)+fib_recursive(n-2)
  end
end

def fib_linear(n)
  a, b = 0, 1
  n.times do
    a, b = b, a+b
  end
  return a
end

def fib_log(n)
  (Matrix[[1,1],[1,0]]**n)[0,1]
end

def omit_bignum(n, dig = 20)
  s = n.to_s
  return s if s.size <= dig+5
  return s[0...dig] + ".{" + (s.size-dig).to_s + "}"
end

[26,27,28,29].each do |n|
  start = Time.now
  f = fib_recursive(n)
  time = Time.now - start
  puts "fib_recursive(#{n}) == #{f}; #{time} secs"
end
[20000,40000,60000,80000,100000].each do |n|
  start = Time.now
  f = fib_linear(n)
  time = Time.now - start
  puts "fib_linear(#{n}) == #{omit_bignum(f,20)}; #{time} secs"
end
[1000,3000,10000,30000,100000,300000].each do |n|
  start = Time.now
  f = fib_log(n)
  time = Time.now - start
  puts "fib_log(#{n}) == #{omit_bignum(f,20)}; #{time} secs"
end

@Python Source

行列演算には、
"matrix.rb"をほぼ全移植したPython向け行列操作ライブラリ"matrix.py" - CanI’s Diary
を使用しています。
以前のソースからは、3.0系での、print関数とかのみが変更点です。
あ、あと、class longが消えたので、matrix.pyも3.0のみ一部修正してあります。

#!/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))

実行環境


さて、結果はこんな感じです。

fib_recursive(再帰)

単位 : secs ruby 1.8.7-p72-i386 ruby 1.9.1-p0-i386 python 2.6.2 python 3.0.1 ironpython 2.02 ironruby 0.6.0
fib_recursive(26) 0.467 0.125 0.1 0.104 0.07 0.289
fib_recursive(27) 0.743 0.201 0.159 0.168 0.082993 0.324
fib_recursive(28) 1.302 0.369 0.256 0.276 0.137009 0.491
fib_recursive(29) 1.858 0.526 0.431 0.448 0.235001 0.807


ruby 1.8.7の遅いな…とか思ってたら1.9できちんと改善されてますね。
まだ、python系の方が早いですが(ぁ
ironpython大勝利!誰だ、.Net遅いって言った奴。
ironrubyもなかなかできる子のようです。将来に期待。

fib_liner(線形)

単位 : secs ruby 1.8.7-p72-i386 ruby 1.9.1-p0-i386 python 2.6.2 python 3.0.1 ironpython 2.02 ironruby 0.6.0
fib_liner(20000) 0.083 0.112 0.069 0.066 0.05201 0.122
fib_liner(40000) 0.346 0.379 0.258 0.254 0.10601 0.119
fib_liner(60000) 0.652 0.797 0.555 0.57 0.209015 0.287
fib_liner(80000) 1.208 1.388 0.98 0.977 0.348991 0.469
fib_liner(100000) 1.57 2.164 1.516 1.56 0.565002 0.733


.Net大勝利!やっぱり、やればできる子です。
それに比べて、ruby姉さんは…1.9でさらに遅くなったようです。

fib_log(行列)

単位 : secs ruby 1.8.7-p72-i386 ruby 1.9.1-p0-i386 python 2.6.2 python 3.0.1 ironpython 2.02 ironruby 0.6.0
fib_log(1000) 0.002 0.001 0.001 0.001 0.147011 0.171
fib_log(3000) 0.002 0.001 0.001 0.001 0.002991 0.022
fib_log(10000) 0.005 0.004 0.002 0.002 0.000999 0.006
fib_log(30000) 0.029 0.036 0.008 0.009 0.016998 0.031
fib_log(100000) 0.334 0.319 0.053 0.054 0.10099 0.098
fib_log(300000) 2.54 2.737 0.316 0.313 0.879997 0.86


ruby姉さんしっかり!
どうしてこんなかかるんだろうね。多倍長計算あたりの差かな。linerとlogの100000とか比べると計算量的には確実に早くなるはずで、事実そうなってるんだけど。matrixが遅いってわけじゃないだろうしね。
pythonさん爆速です。
matrix.pyとか作ったかいがあります。
.Netな方々たちもなかなか。ironrubyたんruby姉さんよりも早いっすよ!
しかし、fib_log(1000)の遅さが気になるなー。初回参照だからかしらん。なんか違う処理してんのかね。

まとめ

各アルゴリズム毎の処理速度をまとめてみるとこんな感じ。(当然、より小さいほうが早い)


ironpython大勝利
ってことですかね。
ruby姉さんがなぜ遅いのか考えてみるのもおもしろそうです。


※環境によっては、画像がぼやけて見えるかと思いますが、縮小されて表示されているためです。
 クリックすると拡大します。