フィボナッチ数で遊ぶ

Programming Ruby

日曜プログラマとしては，フィボナッチ数(wikipedia)を生成する関数くらいは呼吸するかのごとく書けるようになりたいと思ったので，書いてみた．Rubyで．

これがまだdoukaku.orgに投稿されていないのは不思議だなぁ……．

イテレイティブに書いた版

はじめに，wikipediaの定義を見ながら書いてみたのがこれ．安直にループを使って書いている．

#!/usr/bin/env ruby
def fibonacci(f1, f2)
  if f1 == 0 and f2 == 0 then
    return [0, 1]
  end
  return [f2, f1 + f2]
end

maxn = ARGV[0] ? ARGV[0].to_i : 10
arg = [0, 0]
p [:n, :fn]
for n in (1 .. maxn)
  arg = fibonacci(*arg)
  fn = arg[1]
  p [n, fn]
end

リカーシブに書いた版

次に，再起呼び出し(recursive call)を使って書いてみた．

動くことは動くけど，やはりとてつもなく遅い．オーダがO(2^n)だから当然か．

#!/usr/bin/env ruby
def fibonacci(n)
  if n == 1 or n == 2 then
    return 1
  end
  fibonacci(n - 2) + fibonacci(n - 1)
end

maxn = ARGV[0] ? ARGV[0].to_i : 10
p [:n, :fn]
for n in (1..maxn)
  p [n, fibonacci(n)]
end

キャッシュを使った版

一度計算したものをグローバル変数にキャッシュ．これでだいぶ速くなった．

fibonacci(100)を初めて計算する時に，1〜99がキャッシュに入っていないような状況だと，やはり時間はかかるけど．

#!/usr/bin/env ruby
$CACHE = []

def fibonacci_do(n)
  if n == 1 or n == 2 then
    return 1
  end
  fibonacci(n - 2) + fibonacci(n - 1)
end

def fibonacci(n)
  $CACHE[n] ||= fibonacci_do(n)
end

maxn = ARGV[0] ? ARGV[0].to_i : 10
p [:n, :fn]
for n in (1..maxn)
  p [n, fibonacci(n)]
end

キャッシュ使用版を基に，クラス化した版

キャッシュにグローバル変数を使うのがいまいちなので，クラス変数にした版．

#!/usr/bin/env ruby
class Fibonacci
  @@cache = []

  def calc(n)
    @@cache[n] ||= func(n)
  end

  private
  def func(n)
    return 1 if n == 1 or n == 2
    calc(n - 2) + calc(n - 1)
  end
end

maxn = ARGV[0] ? ARGV[0].to_i : 10
fibonacci = Fibonacci.new
p [:n, :fn]
for n in (1..maxn)
  p [n, fibonacci.calc(n)]
end

末尾再帰版

末尾再帰ふうの書き方で書きなおしてみた．i=1からn==iになるまでi++しながら計算している．

キャッシュはあるものの，全く活用できていないのがいけていない．

#!/usr/bin/env ruby
class Fibonacci
  @@cache = []

  def calc(n)
    @@cache[n] ||= func(n, 1, 0, 0)
  end

  private
  def func(n, i, f1, f2)
    f1, f2 = 0, 1 if i == 1 or i == 2
    if i < n then
      return func(n, i + 1, f2, f1 + f2)
    end
    return f1 + f2
  end
end

maxn = ARGV[0] ? ARGV[0].to_i : 10
fibonacci = Fibonacci.new
p [:n, :fn]
for n in (1..maxn)
  p [n, fibonacci.calc(n)]
end

末尾再帰 + キャッシュ改良版

末尾再帰版をもとに改良．

最初に，与えられたnに一番近い値をキャッシュから拾ってきて，そこから計算を開始するようにした．

特別扱いをする必要があるn=0, 1, 2の場合を，最初からキャッシュに突っ込んでおくことにより条件分岐を減らしたあたりがチャームポイント．

#!/usr/bin/env ruby
class Fibonacci
  @@cache = [0, 1, 1]

  def calc(n)
    @@cache[n] ||= func(n, n0 = find_cache(n-1),
                           *@@cache[n0-2..n0-1])
  end

  private
  def find_cache(n)
    return find_cache(n - 1) if @@cache[n].nil?
    return n
  end

  def func(n, i, f1, f2)
    @@cache[i] = r = f1 + f2
    return r if i == n
    return func(n, i + 1, f2, r)
  end
end

maxn = ARGV[0] ? ARGV[0].to_i : 10
fibonacci = Fibonacci.new
p [:n, :fn]
for n in (1..maxn)
  p [n, fibonacci.calc(n)]
end

まとめ

フィボナッチ数の生成は手あかのついたテーマだと思うが，自分で作ってみるといろいろと工夫するべきポイントが見えてきて面白い．やはり，自分で一度やってみる，ということは重要だと思った．