about summary refs log tree commit diff
path: root/scratch
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-07-01T14·13+0100
committerWilliam Carroll <wpcarro@gmail.com>2020-07-01T14·13+0100
commit155dff562ac5c9d893ace858c4a41a2d89955097 (patch)
tree441b57821867b23294c5818d194f6651097fdb05 /scratch
parenta8b3a2d3c0aad932c650e60959b6afab7d3fa018 (diff)
Impl part 3/3 for Memo
Refactor the caching policy for the Memo by evicting the elements that have been
the least-recently-accessed.

Python's heapq module default to a min-heap. By storing our heap elements
as (UnixTime, a), we can guarantee that when we call heappop, we will get the
element with the lowest UnixTime value in heap (i.e. the oldest). When we call
heappush, we use (time.time(), key) and these values -- by having the largest
UnixTime, will propogate to the bottom of the min-heap.
Diffstat (limited to 'scratch')
-rw-r--r--scratch/data_structures_and_algorithms/memo.py39
1 files changed, 10 insertions, 29 deletions
diff --git a/scratch/data_structures_and_algorithms/memo.py b/scratch/data_structures_and_algorithms/memo.py
index 21b85ea71761..44ea93e1bd49 100644
--- a/scratch/data_structures_and_algorithms/memo.py
+++ b/scratch/data_structures_and_algorithms/memo.py
@@ -1,40 +1,19 @@
 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
+from heapq import heappush, heappop
 
 
 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.
+        members. Memo evicts the least-recently-accessed 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)
+        self.heap = [(0, None)] * size
 
     def contains(self, k):
         """
@@ -46,19 +25,21 @@ class Memo(object):
         """
         Return the memoized item at key `k`.
         """
+        # "touch" the element in the heap
         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]
+        _, to_evict = heappop(self.heap)
+        if to_evict != None:
+            del self.xs[to_evict]
+        heappush(self.heap, (time.time(), k))
         self.xs[k] = v
 
 
-memo = Memo(size=3)
+memo = Memo(size=10)
 
 
 def f(x):