Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
recursive memoization with hashes
require 'benchmark'
def factorial(x)
x == 1 ? 1 : x * factorial(x-1)
end
factorial_hash ||= Hash.new do |hash,key|
key == 1 ? (key = 1) : (hash[key] = key * hash[key-1])
end
def fibonacci(n)
n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2)
end
fib_hash ||= Hash.new do |hash,key|
hash[key] = hash[key-1] + hash[key-2]
end
# initalise special cases
fib_hash[1] = 1; fib_hash[2] = 1
Benchmark.bm do |bm|
puts "---------- factorial benchmarks -------------"
n = 3000
bm.report(:factorial) { factorial(n) }
bm.report(:factorial) { factorial(n) }
bm.report(:factorial_hash) { factorial_hash[n] }
bm.report(:factorial_hash) { factorial_hash[n] }
puts "---------- fibonacci benchmarks -------------"
n = 35
bm.report(:fibonacci) { fibonacci(n) }
bm.report(:fibonacci) { fibonacci(n) }
bm.report(:fibonacci_hash) { fib_hash[n] }
bm.report(:fibonacci_hash) { fib_hash[n] }
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.