Because the policy is just an object the cache holds, you can replace it at runtime — start with FIFO under light load, switch to LFU when traffic spikes, all without disturbing the cached data. To make the new policy correct, seed it with the keys already in the cache.
set_policy(policy) — replace the eviction strategy and register every current key with it (in insertion order)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
self._store = {}
def get(self, key):
if key in self._store:
self.policy.on_access(key)
return self._store[key]
return None
def put(self, key, value):
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)
def set_policy(self, policy):
"""Swap the eviction strategy, seeding it with the current keys."""
# TODO:
# self.policy = policy
# for key in self._store:
# policy.on_insert(key)
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
Because the policy is just an object the cache holds, you can replace it at runtime — start with FIFO under light load, switch to LFU when traffic spikes, all without disturbing the cached data. To make the new policy correct, seed it with the keys already in the cache.
set_policy(policy) — replace the eviction strategy and register every current key with it (in insertion order)Press Run Tests or ⌘↩ to check your solution.