about summary refs log tree commit diff
path: root/scratch
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-07-01T13·59+0100
committerWilliam Carroll <wpcarro@gmail.com>2020-07-01T13·59+0100
commita8b3a2d3c0aad932c650e60959b6afab7d3fa018 (patch)
tree86276249a446677ffa89774f95a9df8e98ece1b1 /scratch
parentec7c8516f7443e76233aa0f44d06c074f88498f0 (diff)
Support part 2/3 for the Memo problem
Bound the size of the memo by creating a BoundedQueue. Whenever we add elements
to the BoundedQueue, we remove the oldest elements. We use the BoundedQueue to
control the size of our dictionary that we're using to store our key-value pairs.
Diffstat (limited to 'scratch')
-rw-r--r--scratch/data_structures_and_algorithms/memo.py68
1 files changed, 64 insertions, 4 deletions
diff --git a/scratch/data_structures_and_algorithms/memo.py b/scratch/data_structures_and_algorithms/memo.py
index 8195f32c931c..21b85ea71761 100644
--- a/scratch/data_structures_and_algorithms/memo.py
+++ b/scratch/data_structures_and_algorithms/memo.py
@@ -1,18 +1,78 @@
 import time
 import random
+from collections import deque
 
-memo = {}
+
+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):
-    if x in memo:
+    """
+    Compute some mysterious, expensive function.
+    """
+    if memo.contains(x):
         print("Hit.\t\tf({})".format(x))
-        return memo[x]
+        return memo.get(x)
     else:
         print("Computing...\tf({})".format(x))
         time.sleep(0.25)
         res = random.randint(0, 10)
-        memo[x] = res
+        memo.set(x, res)
         return res