Cache Eviction (Strategy Pattern)Step 4 of 5

The Cache

12345

Step 4 — The Cache

Now the payoff: a Cache that knows nothing about how eviction is decided — it just holds data and delegates the choice to whatever policy it was handed. The same cache class works with FIFO, LRU, or LFU, and that is the whole point of the Strategy pattern.

  • get(key) — return the value (and record an access) or None on a miss
  • put(key, value) — insert or update; when a new key would exceed capacity, ask the policy for a victim and evict it first
Hints
Starter code
class EvictionPolicy:
    def on_insert(self, key):
        raise NotImplementedError

    def on_access(self, key):
        raise NotImplementedError

    def evict(self):
        raise NotImplementedError


class FIFOPolicy(EvictionPolicy):
    def __init__(self):
        self._order = []

    def on_insert(self, key):
        self._order.append(key)

    def on_access(self, key):
        pass

    def evict(self):
        return self._order.pop(0)


class LRUPolicy(EvictionPolicy):
    def __init__(self):
        self._order = []

    def on_insert(self, key):
        self._order.append(key)

    def on_access(self, key):
        if key in self._order:
            self._order.remove(key)
        self._order.append(key)

    def evict(self):
        return self._order.pop(0)


class LFUPolicy(EvictionPolicy):
    def __init__(self):
        self._counts = {}
        self._order = []

    def on_insert(self, key):
        self._counts[key] = 1
        self._order.append(key)

    def on_access(self, key):
        self._counts[key] = self._counts.get(key, 0) + 1

    def evict(self):
        victim = min(self._order, key=lambda k: self._counts[k])
        self._order.remove(victim)
        del self._counts[victim]
        return victim


class Cache:
    def __init__(self, capacity, policy):
        self.capacity = capacity
        self.policy = policy        # any EvictionPolicy
        self._store = {}

    def get(self, key):
        """Return the value for key, recording an access; None if absent."""
        # TODO:
        #   if key in self._store:
        #       self.policy.on_access(key)
        #       return self._store[key]
        #   return None
        pass

    def put(self, key, value):
        """Insert or update key; evict via the policy when over capacity."""
        # TODO:
        #   if key in self._store:
        #       self._store[key] = value
        #       self.policy.on_access(key)
        #       return
        #   if len(self._store) >= self.capacity:
        #       victim = self.policy.evict()
        #       del self._store[victim]
        #   self._store[key] = value
        #   self.policy.on_insert(key)
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step