ruby lookup table using Hash
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#Lookup Tables, http://en.wikipedia.org/wiki/Lookup_table | |
#Memoization, http://en.wikipedia.org/wiki/Memoization | |
require 'benchmark' | |
########################################################### | |
# Fibonacci number, http://en.wikipedia.org/wiki/Fibonacci_number | |
def fib(n) | |
n < 2 ? 1 : fib(n-2) + fib(n-1) | |
end | |
fib_lut = Hash.new do |lut, n| | |
lut[n] = n < 2 ? 1 : lut[n-2] + lut[n-1] | |
end | |
fib(30) # => 10946 | |
fib_lut[30] # => 10946 | |
Benchmark.measure{fib(37)} #=> 7.710000 0.000000 7.710000 ( 7.710386) | |
Benchmark.measure{fib(37)} #=> 7.700000 0.000000 7.700000 ( 7.702327) | |
Benchmark.measure{fib_lut[37]} #=> 0.000000 0.000000 0.000000 ( 0.000109) | |
Benchmark.measure{fib_lut[37]} #=> 0.000000 0.000000 0.000000 ( 0.000011) | |
Benchmark.measure{fib_lut[1000]} #=> 0.000000 0.000000 0.000000 ( 0.003615) | |
Benchmark.measure{fib_lut[1000]} #=> 0.000000 0.000000 0.000000 ( 0.000012) | |
fib_lut[1000] #=> 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501 | |
########################################################### | |
# Factorial, http://en.wikipedia.org/wiki/Factorial | |
def fact(n) | |
n == 0 ? 1 : n * fact(n-1) | |
end | |
fact_lut = Hash.new do |lut, n| | |
1.upto(n-1).each{|i| lut[i]} # avoid "stack level too deep" | |
lut[n] = n == 0 ? 1 : n * lut[n-1] | |
end | |
fact(30) # => 265252859812191058636308480000000 | |
fact_lut[30] # => 265252859812191058636308480000000 | |
Benchmark.measure{fact(7000)} #=> 0.180000 0.000000 0.180000 ( 0.183354) | |
Benchmark.measure{fact(7000)} #=> 0.180000 0.000000 0.180000 ( 0.185808) | |
Benchmark.measure{fact_lut[7000]} #=> 4.530000 0.030000 4.560000 ( 4.558187) | |
Benchmark.measure{fact_lut[7000]} #=> 0.000000 0.000000 0.000000 ( 0.000012) | |
# fact(10000) => "stack level too deep" | |
fact_lut[10000] #=> number with 35660 digits: starting with 28462596809... and having 2499 zeros in the end | |
########################################################### | |
# Ackermann function, http://en.wikipedia.org/wiki/Ackermann_function | |
def ack(m, n) | |
return n + 1 if m == 0 | |
return ack(m - 1, 1) if m > 0 && n == 0 | |
return ack(m - 1, ack(m, n-1)) if m > 0 && n > 0 | |
end | |
ack_lut = Hash.new do |lut, mn| | |
lut[mn] = mn[1] + 1 if mn[0] == 0 | |
lut[mn] = lut[[mn[0] - 1, 1]] if mn[0] > 0 && mn[1] == 0 | |
lut[mn] = lut[[mn[0] - 1, lut[[mn[0], mn[1]-1]]]] if mn[0] > 0 && mn[1] > 0 | |
lut[mn] | |
end | |
ack(3,6) # => 509 | |
ack_lut[[3,6]] # => 509 | |
Benchmark.measure{ack(3,9)} #=> 1.440000 0.000000 1.440000 ( 1.433464) | |
Benchmark.measure{ack(3,9)} #=> 1.430000 0.000000 1.430000 ( 1.433389) | |
Benchmark.measure{ack_lut[[3,9]]} #=> 0.050000 0.000000 0.050000 ( 0.044746) | |
Benchmark.measure{ack_lut[[3,9]]} #=> 0.000000 0.000000 0.000000 ( 0.000033) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment