Trampoline Example

gistfile1.py

#!/usr/bin/python

import time

def fib(n):
  if n < 2: return n
  else: return fib(n - 1) + fib(n - 2)

def fast_fib(n, a, b):
  if n == 0: return a
  else: return fast_fib(n - 1, b, a + b)

def trampoline(f):
  while callable(f):
    f = f()
  return f

def tramp_fib(n, a, b):
  if n == 0: return a
  else: return lambda: tramp_fib(n - 1, b, a + b)

def iter_fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

def timeit(times, f, *args, **kwargs):
  def run():
    start = time.time()
    f(*args, **kwargs)
    return time.time() - start
  results = sorted([run() for _ in range(times)])
  return {
    "min": min(results),
    "max": max(results),
    "avg": sum(results) / times,
    "median": results[int(times*0.5+0.5)],
    "95th": results[int(times*0.95+0.5)],
    "99th": results[int(times*0.99+0.5)]
  }

def format_stats(stats):
  keys = ["avg", "min", "median", "95th", "99th", "max"]
  return ", ".join(["%s: %0.6fs" % (k, stats[k]) for k in keys])

TIMES = 1000
print "Naive (25):\t\t", format_stats(timeit(TIMES, fib, 25))
print "Recursive (50):\t\t", format_stats(timeit(TIMES, fast_fib, 50, 0, 1))
print "Iterative (10000):\t", format_stats(timeit(TIMES, iter_fib, 10000))
print "Trampoline (10000):\t", format_stats(timeit(TIMES, trampoline, lambda: tramp_fib(10000, 0, 1)))