Various methods of memoization in Ruby

Question

If you are a ruby ​​programmer, you might come across a hash block memoization pattern. For a simple example, I present to you a memorialized version of the Fibonacci sequence:

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 

Of course, this is not the only way to create a memoized version of the Fibonacci sequence. You can also do the following:

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

I hope you see how the hash block memoization pattern maps to the second version, which is much more common in many other languages. I would like to know if there is a difference between the two versions? I can't shake the feeling that the hash block version is more efficient, but I can't really justify why.

Answer 1

The test in MRI 1.8.7 gives:

• Hash block: 0.44 seconds
• No hash block: 0.41 seconds

And in MRI 1.9.0:

• Hash block: 0.24 seconds
• No hash block: 0.28 seconds

The test consists of 100 iterations of calculating Fibonacci numbers from 1 to 1000, flushing a hash or cache at the beginning of each iteration.

Here's a benchmark for a hash block:

 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 

Here's a benchmark for a block without a hash:

 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