4

あなたがルビープログラマーなら、ハッシュブロックのメモ化パターンに出くわしたかもしれません。簡単な例として、フィボナッチ数列のメモ化バージョンを紹介します。

fib_hash = Hash.new do |h,i|
  h[i] = h[i-1] + h[i-2]
end
# establish the base cases
fib_hash[1] = 1; fib_hash[2] = 1

もちろん、これがフィボナッチ数列のメモ化バージョンを作成する唯一の方法ではありません。次のこともできます。

@cache = {}; @cache[1] = 1; @cache[2] = 1
def memo_fib(n)
  @cache[n] ||= (memo_fib(n-1) + memo_fib(n-2))
end

うまくいけば、ハッシュブロックのメモ化パターンが他の多くの言語ではるかに一般的な2番目のバージョンにどのようにマッピングされるかがわかります。私が知りたいのは、2つのバージョンの間に違いがあるかどうかです。ハッシュブロックバージョンの方が効率的だという気持ちを揺るがすことはできませんが、その理由を正当化することはできません。

4

1 に答える 1

5

MRI 1.8.7のベンチマークでは、次の結果が得られます。

  • ハッシュブロック：0.44秒
  • 非ハッシュブロック：0.41秒

そしてMRI1.9.0では：

  • ハッシュブロック：0.24秒
  • 非ハッシュブロック：0.28秒

ベンチマークは、1から1000までのフィボナッチ数を計算する100回の反復であり、各反復の開始時にハッシュまたはキャッシュをリセットします。

ハッシュブロックのベンチマークは次のとおりです。

def reset_fib_hash                                                              
  @fib_hash = Hash.new do |h,i|
    h[i] = h[i-1] + h[i-2]
  end
  # establish the base cases                                                    
  @fib_hash[1] = 1; @fib_hash[2] = 1
end

start_time = Time.now
100.times do
  reset_fib_hash
  (1..1000).each do |i|
    @fib_hash[i]
  end
end
p Time.now - start_time

非ハッシュブロックのベンチマークは次のとおりです。

def reset_fib_hash
  @cache = {}; @cache[1] = 1; @cache[2] = 1
end

def memo_fib(n)
  @cache[n] ||= (memo_fib(n-1) + memo_fib(n-2))
end

start_time = Time.now
100.times do
  reset_fib_hash
  (1..1000).each do |i|
    memo_fib(i)
  end
end
p Time.now - start_time
于 2011-02-27T00:57:27.527 に答える