LRU CacheStep 5 of 5

Hit / Miss Statistics

12345

Step 5 — Hit / Miss Statistics

Caches live and die by their hit rate. Instrument get to record whether each lookup was a hit (key present) or a miss (absent), and expose the numbers.

  • count a hit / miss on every get
  • stats() — return {"hits": h, "misses": m, "hit_rate": r}, where hit_rate is hits / (hits + misses), or 0.0 when there have been no lookups

Only get counts — peek and put don't touch the stats. The counters (_hits, _misses) are already initialized for you.

Hints
Starter code
class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self._map = {}
        self._head = Node()
        self._tail = Node()
        self._head.next = self._tail
        self._tail.prev = self._head
        self._hits = 0
        self._misses = 0

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):
        node.next = self._head.next
        node.prev = self._head
        self._head.next.prev = node
        self._head.next = node

    def get(self, key):
        if key not in self._map:
            # TODO: count a miss, then return None
            return None
        # TODO: count a hit
        node = self._map[key]
        self._remove(node)
        self._add_front(node)
        return node.value

    def put(self, key, value):
        if key in self._map:
            node = self._map[key]
            node.value = value
            self._remove(node)
            self._add_front(node)
            return
        node = Node(key, value)
        self._map[key] = node
        self._add_front(node)
        if len(self._map) > self.capacity:
            lru = self._tail.prev
            self._remove(lru)
            del self._map[lru.key]

    def stats(self):
        """Return {"hits": ..., "misses": ..., "hit_rate": ...}."""
        # TODO:
        #   total = self._hits + self._misses
        #   rate = self._hits / total if total else 0.0
        #   return the dict
        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.

PreviousAll challenges