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

アルゴリズムの違いが速度に明確に表れるわかりやすい例のひとつであるフィボナッチ数列を使って速度比較。

気軽に多倍長が使える言語でないと、線形とlogの違いは見えづらい。

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

fib_recursive(26) == 121393; 1.012822 secs
fib_recursive(27) == 196418; 1.57305 secs
fib_recursive(28) == 317811; 2.504721 secs
fib_recursive(29) == 514229; 4.074175 secs
fib_linear(20000) == 25311623237323612422.{4160}; 0.111655 secs
fib_linear(40000) == 14326001654578073438.{8340}; 0.32405 secs
fib_linear(60000) == 81083035047844154209.{12519}; 0.65209 secs
fib_linear(80000) == 45891789845416942428.{16699}; 1.089483 secs
fib_linear(100000) == 25974069347221724166.{20879}; 1.649962 secs
fib_log(1000) == 43466557686937456435.{189}; 0.001986 secs
fib_log(3000) == 41061588630797126033.{607}; 0.002331 secs
fib_log(10000) == 33644764876431783266.{2070}; 0.004074 secs
fib_log(30000) == 19042435673462438748.{6250}; 0.020529 secs
fib_log(100000) == 25974069347221724166.{20879}; 0.186566 secs
fib_log(300000) == 87617325329163457942.{62676}; 1.484438 secs

fib_recursive

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

単純な再帰によって実現される方法。O(1.68^n)時間かかるらしい。

fib_linear

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

2つの隣接した要素を保持することで線形時間O(n)で解ける。

fib_log

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

ある行列の冪乗によってフィボナッチ数列が求められることが知られている。

冪乗はO(log(n))回で解けるので、この問題もO(log(n))で解ける。

ただし

ただし、多倍長で計算するので、もう少し時間がかかります。