Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # -*- encoding: utf-8 -*-
- require 'benchmark/ips'
- def fib_naive(n)
- return 1 if n <= 2
- fib_naive(n - 1) + fib_naive(n - 2)
- end
- def fib_memo(n)
- fib_memo_recur(n, {})
- end
- def fib_memo_recur(n, memo)
- return memo[n] if memo.key?(n)
- return memo[n] = 1 if n <= 2
- memo[n] = fib_memo_recur(n - 1, memo) + fib_memo_recur(n - 2, memo)
- end
- def fib_iter_inner(prev2, prev1, cnt)
- if cnt == 1
- prev2 + prev1
- else
- fib_iter_inner(prev1, prev2 + prev1, cnt - 1)
- end
- end
- def fib_iter(n)
- return 1 if n <= 2
- fib_iter_inner(1, 1, n - 2)
- end
- def main
- Benchmark.ips do |x|
- x.config(:time => 5, :warmup => 0)
- x.report('naive') {
- fib_naive(30)
- }
- x.report('memo') {
- fib_memo(30)
- }
- x.report('iter') {
- fib_iter(30)
- }
- end
- end
- case $PROGRAM_NAME
- when __FILE__
- main
- when /spec[^\/]*$/
- # {spec of the implementation}
- end
- # >> Calculating -------------------------------------
- # >> naive 1 i/100ms
- # >> memo 1 i/100ms
- # >> iter 1 i/100ms
- # >> -------------------------------------------------
- # >> naive 9.9 (±0.0%) i/s - 50 in 5.067318s
- # >> memo 80426.9 (±5.0%) i/s - 258215 in 4.200047s
- # >> iter 343313.9 (±7.2%) i/s - 721430 in 2.385844s
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement