# Function memoization using dynamic binding. (1.01)
 
from time import process_time
 
# Class for dynamic binding of a variable.
 
class Parameter:
    def __init__(self, v):
        self.v = v
    def __call__(self):
        return self.v
    def bind(self, v, thunk):
        t = self.v
        self.v = v
        thunk()
        self.v = t
 
# Memo.
 
def setdelayed(m, key, thunk=lambda: None):
    if key not in m:
        m[key] = thunk()
    return m[key]
 
def memo(f, keyfunc=lambda x: x):
    m = {}
    return lambda *args: setdelayed(m, keyfunc(args), lambda: f(*args))
 
# Main.
 
fib = Parameter(lambda n: fib()(n-2) + fib()(n-1) if n > 1 else n)
 
def make_f(f):
    return lambda: fib.bind(f, lambda: print(fib()(30), repr(fib())))
 
def time_f(thunk):
    t = process_time()
    thunk()
    print('Elapsed: {:.6f}s'.format(process_time() - t))
 
time_f(make_f(memo(fib())))
time_f(make_f(fib()))

IyBGdW5jdGlvbiBtZW1vaXphdGlvbiB1c2luZyBkeW5hbWljIGJpbmRpbmcuICgxLjAxKQoKZnJvbSB0aW1lIGltcG9ydCBwcm9jZXNzX3RpbWUKCiMgQ2xhc3MgZm9yIGR5bmFtaWMgYmluZGluZyBvZiBhIHZhcmlhYmxlLgoKY2xhc3MgUGFyYW1ldGVyOgogICAgZGVmIF9faW5pdF9fKHNlbGYsIHYpOgogICAgICAgIHNlbGYudiA9IHYKICAgIGRlZiBfX2NhbGxfXyhzZWxmKToKICAgICAgICByZXR1cm4gc2VsZi52CiAgICBkZWYgYmluZChzZWxmLCB2LCB0aHVuayk6CiAgICAgICAgdCA9IHNlbGYudgogICAgICAgIHNlbGYudiA9IHYKICAgICAgICB0aHVuaygpCiAgICAgICAgc2VsZi52ID0gdAoKIyBNZW1vLgoKZGVmIHNldGRlbGF5ZWQobSwga2V5LCB0aHVuaz1sYW1iZGE6IE5vbmUpOgogICAgaWYga2V5IG5vdCBpbiBtOgogICAgICAgIG1ba2V5XSA9IHRodW5rKCkKICAgIHJldHVybiBtW2tleV0KCmRlZiBtZW1vKGYsIGtleWZ1bmM9bGFtYmRhIHg6IHgpOgogICAgbSA9IHt9CiAgICByZXR1cm4gbGFtYmRhICphcmdzOiBzZXRkZWxheWVkKG0sIGtleWZ1bmMoYXJncyksIGxhbWJkYTogZigqYXJncykpCgojIE1haW4uCgpmaWIgPSBQYXJhbWV0ZXIobGFtYmRhIG46IGZpYigpKG4tMikgKyBmaWIoKShuLTEpIGlmIG4gPiAxIGVsc2UgbikKCmRlZiBtYWtlX2YoZik6CiAgICByZXR1cm4gbGFtYmRhOiBmaWIuYmluZChmLCBsYW1iZGE6IHByaW50KGZpYigpKDMwKSwgcmVwcihmaWIoKSkpKQoKZGVmIHRpbWVfZih0aHVuayk6CiAgICB0ID0gcHJvY2Vzc190aW1lKCkKICAgIHRodW5rKCkKICAgIHByaW50KCdFbGFwc2VkOiB7Oi42Zn1zJy5mb3JtYXQocHJvY2Vzc190aW1lKCkgLSB0KSkKCnRpbWVfZihtYWtlX2YobWVtbyhmaWIoKSkpKQp0aW1lX2YobWFrZV9mKGZpYigpKSk=