blob: 21b85ea71761e403fae46d56f3a0eb3a39379ee4 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
import time
import random
from collections import deque
class BoundedQueue(object):
def __init__(self, size=0):
"""
Returns a queue of elements that will never exceed `size`
members. BoundedQueue evicts the oldest elements from itself before
adding new elements.
"""
self.xs = deque([None] * size)
def add(self, x):
"""
Add element `x` to the end of the queue. Evict the oldest element from
the queue.
"""
evicted = None
if self.xs:
evicted = self.xs.popleft()
self.xs.append(x)
return evicted
class Memo(object):
def __init__(self, size=1):
"""
Create a key-value data-structure that will never exceed `size`
members. Memo evicts the oldest elements from itself before adding
inserting new key-value pairs.
"""
if size <= 0:
raise Exception("We do not support an empty memo")
self.xs = {}
self.q = BoundedQueue(size=size)
def contains(self, k):
"""
Return true if key `k` exists in the Memo.
"""
return k in self.xs
def get(self, k):
"""
Return the memoized item at key `k`.
"""
return self.xs[k]
def set(self, k, v):
"""
Memoize value `v` at key `k`.
"""
evicted = self.q.add(k)
if evicted != None:
del self.xs[evicted]
self.xs[k] = v
memo = Memo(size=3)
def f(x):
"""
Compute some mysterious, expensive function.
"""
if memo.contains(x):
print("Hit.\t\tf({})".format(x))
return memo.get(x)
else:
print("Computing...\tf({})".format(x))
time.sleep(0.25)
res = random.randint(0, 10)
memo.set(x, res)
return res
[f(random.randint(0, 10)) for _ in range(10)]
|
