fork download
copy 
  1. # Function memoization using dynamic binding. (1.02)
  2.  
  3. from time import process_time
  4.  
  5. # Class for dynamic binding of a variable.
  6.  
  7. class Parameter:
  8.     def __init__(self, v):
  9.         self.v = v
  10.     def __call__(self):
  11.         return self.v
  12.     def bind(self, v, thunk):
  13.         t = self.v
  14.         self.v = v
  15.         thunk()
  16.         self.v = t
  17.  
  18. # Memo.
  19.  
  20. def setdelayed(m, key, thunk=lambda: None):
  21.     if key not in m:
  22.         m[key] = thunk()
  23.     return m[key]
  24.  
  25. def memo(f, keyfunc=lambda x: x):
  26.     m = {}
  27.     def wrapper(*args):
  28.         return setdelayed(m, keyfunc(args), lambda: f(*args))
  29.     return wrapper
  30.  
  31. def lru_memo(f, maxsize=128, keyfunc=lambda x: x):
  32.     m = {}
  33.     def wrapper(*args):
  34.         k = keyfunc(args)
  35.         if k in m:
  36.             m[k] = v = m.pop(k)
  37.         else:
  38.             m[k] = v = f(*args)
  39.             if len(m) > maxsize:
  40.                 del m[next(iter(m))]
  41.         return v
  42.     return wrapper
  43.  
  44. # Main.
  45.  
  46. fib = Parameter(lambda n: fib()(n-2) + fib()(n-1) if n > 1 else n)
  47.  
  48. def make_f(f):
  49.     return lambda: fib.bind(f, lambda: print(fib()(30), repr(fib())))
  50.  
  51. def time_f(thunk):
  52.     t = process_time()
  53.     thunk()
  54.     print('Elapsed: {:.6f}s'.format(process_time() - t))
  55.  
  56. time_f(make_f(lru_memo(fib(), 2)))
  57. time_f(make_f(memo(fib())))
  58. time_f(make_f(fib()))
Success #stdin #stdout 0.58s 14140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
832040 <function lru_memo.<locals>.wrapper at 0x14a259532b60>
Elapsed: 0.000000s
832040 <function memo.<locals>.wrapper at 0x14a259532c00>
Elapsed: 0.000000s
832040 <function <lambda> at 0x14a259532980>
Elapsed: 0.489441s
https://ideone.com/JFlU8o
language:
Python 3 (python  3.12)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!