CODEWITHSUNDEEP
rubymemoization
Jikku Jose
Jikku Jose

Reputation: 18804

Memoization techniques

While trying some memoization techniques I stumbled on this benchmark results which is against my expectations. Seems I am making some silly mistake, does someone see what I am doing wrong here (the benchmark gives similar results for memoized and non memoized code)?

require 'benchmark'

# -----------------------------------------

class FactorialClass

  @@sequence = [1]

  def self.of( n )
    @@sequence[n] || n * of( n - 1 )
  end

end

# -----------------------------------------

def factorial_with_memoization
  sequence = [1]
  lambda = Proc.new do |n|
    sequence[n] || n * lambda.call( n - 1 )
  end
end
f = factorial_with_memoization()

# -----------------------------------------

def factorial n
 n == 0 ? 1 : n * factorial( n - 1 )
end

# -----------------------------------------



count = 1_000
n = 1000

without_memoization = Benchmark.measure do
  count.times do 
    factorial(n)
  end
end

with_memoization_lambda = Benchmark.measure do
  count.times do 
    f.call(n)
  end
end

with_memoization_class = Benchmark.measure do
  count.times do 
    FactorialClass.of(n)
  end
end


puts "Without memoization           : #{ without_memoization }"
puts "With memoization using lambda : #{ with_memoization_lambda }"
puts "With memoization using class  : #{ with_memoization_class }"

** The results are: **

Without memoization           :   1.210000   0.100000   1.310000 (  1.309675)
With memoization using lambda :   1.750000   0.100000   1.850000 (  1.858737)
With memoization using class  :   1.270000   0.090000   1.360000 (  1.358375)

Upvotes: 1

Views: 254

Answers (1)

Arie Xiao
Arie Xiao

Reputation: 14082

You never assign any memorized value to the cache. As @xlembouras said, you didn't memorize anything.

class FactorialClass
  @@sequence = [1]

  def self.of( n )
    # @@sequence[n] get evaluated to nil unless n is 0, always!
    @@sequence[n] || n * of( n - 1 )
  end
end

You need to manually assign memorized value to the cache, after you finish the computation.

class FactorialClass
  @@sequence = [1]

  def self.of( n )
    @@sequence[n] = (@@sequence[n] || n * of( n - 1 ))
  end
end

However, does memorization really works for your factorial computation? No.

f(n) = n * f(n-1) = n * ((n-1) * f(n-2)) = ... = n * ((n-1) * (... * (3 * f(2))))

All the recursion step calculates the factorial of a new value (from 2 to n), which hasn't been calculated before. The memorization won't get hit at any step.

Upvotes: 2

Related Questions