Skip to content

Instantly share code, notes, and snippets.

@SegFaultAX
Created July 20, 2013 08:14
Show Gist options
  • Save SegFaultAX/6044290 to your computer and use it in GitHub Desktop.
Save SegFaultAX/6044290 to your computer and use it in GitHub Desktop.
Trampoline Example
#!/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)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment