LFU cache in O(1) with frequency buckets

"""The brute force: each cached dish keeps its price, its use count and the time of its last use, and an eviction
compares every cached dish to find the smallest (count, last use). The counter `compared` adds those comparisons up."""
import json


class BruteDishCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.entries = {}  # dish -> [price, count, last_use]
        self.clock = 0  # one tick per call, so a larger last_use is a more recent use
        self.compared = 0

    def _use(self, dish):
        self.clock += 1
        entry = self.entries[dish]
        entry[1] += 1
        entry[2] = self.clock

    def get(self, dish):
        if dish not in self.entries:
            return -1
        self._use(dish)
        return self.entries[dish][0]

    def put(self, dish, price):
        if self.capacity == 0:
            return None
        if dish in self.entries:
            self.entries[dish][0] = price
            self._use(dish)
            return None
        if len(self.entries) == self.capacity:
            self.compared += len(self.entries)
            victim = min(self.entries, key=lambda d: (self.entries[d][1], self.entries[d][2]))
            del self.entries[victim]
        self.clock += 1
        self.entries[dish] = [price, 1, self.clock]
        return None


def replay(ops, args):
    """Runs a test written as in the statement: operation names, their arguments, one answer per call."""
    cache, answers = None, []
    for op, a in zip(ops, args):
        if op == "DishCache":
            cache = BruteDishCache(*a)
            answers.append(None)
        else:
            answers.append(getattr(cache, op)(*a))
    return answers


def lunch_rush(capacity):
    """Fills the cache, then puts 2 x capacity dishes it has never seen: every one of them evicts."""
    cache = BruteDishCache(capacity)
    for dish in range(1, capacity + 1):
        cache.put(dish, dish % 300 + 20)
    for dish in range(capacity + 1, 3 * capacity + 1):
        cache.put(dish, dish % 300 + 20)
    return cache.compared


if __name__ == "__main__":
    print(json.dumps(replay(
        ["DishCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"],
        [[2], [101, 40], [102, 25], [101], [103, 60], [102], [103], [104, 30], [101], [103], [104]],
    )))
    print(json.dumps(replay(["DishCache", "put", "put", "get", "put", "get", "get"], [[1], [7, 15], [7, 18], [7], [9, 20], [7], [9]])))
    print(json.dumps(replay(["DishCache", "put", "get"], [[0], [5, 10], [5]])))
    print()
    print(f"{'capacity':>8} {'new dishes':>11} {'dishes compared':>16} {'per call':>9}")
    for capacity in (250, 500, 1_000, 2_000):
        compared = lunch_rush(capacity)
        print(f"{capacity:>8,} {2 * capacity:>11,} {compared:>16,} {compared / (2 * capacity):>9,.0f}")
    print(f"at capacity 100,000 with 200,000 new dishes: {100_000 * 200_000:,} comparisons")

[null, null, null, 40, null, -1, 60, null, -1, 60, 30]
[null, null, null, 18, null, -1, 20]
[null, null, -1]

capacity  new dishes  dishes compared  per call
     250         500          125,000       250
     500       1,000          500,000       500
   1,000       2,000        2,000,000     1,000
   2,000       4,000        8,000,000     2,000
at capacity 100,000 with 200,000 new dishes: 20,000,000,000 comparisons