about summary refs log tree commit diff
path: root/scratch/data_structures_and_algorithms/memo.py
blob: 44ea93e1bd49cb1e553ac4069a0f95eb8f3a8e8a (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
import time
import random
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 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.heap = [(0, None)] * 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`.
        """
        # "touch" the element in the heap
        return self.xs[k]

    def set(self, k, v):
        """
        Memoize value `v` at key `k`.
        """
        _, 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=10)


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)]