Skip to content

Instantly share code, notes, and snippets.

@knugie
Last active December 24, 2015 02:29
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save knugie/6731009 to your computer and use it in GitHub Desktop.
ruby lookup table using Hash
#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