"""Stdlib-only tests (no pytest): plain asserts in functions called from a __main__ block. Run: `python3 test_lru_cache.py`. The headline tests pin the exact numbers this toy's commentary quotes — the Zipf result in section 6.1 and the collapse in section 6.2 — so the page cannot rot silently. The rest are small unit checks on each policy alone. """ import random from lru_cache import LRUCache, LFUCache from demo import (CAPACITY, HOT_A, HOT_B, PHASE_REQUESTS, SEED, hot_cold_trace, replay, scan_trace, zipf_trace) def two_phase_traces(): """The exact traces demo.py part 2 uses.""" rng = random.Random(SEED) return (hot_cold_trace(rng, HOT_A, PHASE_REQUESTS), hot_cold_trace(rng, HOT_B, PHASE_REQUESTS)) # --------------------------------------------------------------- LRU units -- def test_lru_evicts_the_tail_not_the_oldest_insert(): """`a` is inserted first but used last, so `b` is the victim.""" cache = LRUCache(2) cache.put("a", 1) cache.put("b", 2) cache.get("a") # promotes a; b is now at the tail cache.put("c", 3) assert cache.keys() == ["c", "a"], cache.keys() assert cache.get("b") is None def test_lru_get_reorders_the_list(): """A read, with no write at all, changes who dies next.""" cache = LRUCache(3) for key in "abc": cache.put(key, 1) assert cache.keys() == ["c", "b", "a"] cache.get("b") assert cache.keys() == ["b", "c", "a"] def test_lru_links_stay_consistent_under_churn(): """Walk the list forwards and backwards; both must match the map.""" cache = LRUCache(4) for key in range(20): if cache.get(key) is None: cache.put(key, 1) cache.get(key % 3) forward, node = [], cache.head.next while node is not cache.tail: forward.append(node.key) node = node.next backward, node = [], cache.tail.prev while node is not cache.head: backward.append(node.key) node = node.prev assert forward == list(reversed(backward)), (forward, backward) assert sorted(forward) == sorted(cache.map) assert len(forward) == 4 # --------------------------------------------------------------- LFU units -- def test_lfu_keeps_the_frequently_used_key(): """Three hits on `a` outrank two newcomers arriving after it.""" cache = LFUCache(2) cache.put("a", 1) cache.get("a") cache.get("a") cache.put("b", 2) # b enters at count 1 cache.put("c", 3) # evicts b (count 1) — not a (count 3) assert cache.keys() == ["c", "a"], cache.keys() assert cache.counts == {"a": 3, "c": 1}, cache.counts def test_lfu_breaks_count_ties_by_arrival_order(): """Two keys at the same count: the one that got there first loses.""" cache = LFUCache(2) cache.put("a", 1) cache.put("b", 2) # both at count 1 cache.put("c", 3) assert "a" not in cache.values and "b" in cache.values, cache.keys() def test_lfu_min_count_returns_to_one_after_an_insert(): """The invariant that makes eviction O(1) and correct.""" cache = LFUCache(2) cache.put("a", 1) for _ in range(50): cache.get("a") # a climbs to count 51, min_count follows to 51 assert cache.min_count == 51 cache.put("b", 2) # a newcomer resets the floor assert cache.min_count == 1 cache.put("c", 3) # so the victim is b, not a assert cache.keys() == ["c", "a"], cache.keys() # -------------------------------------------------------- headline results -- def test_lfu_wins_on_a_stationary_zipf_trace(): """Section 6.1: the result everyone expects.""" trace = zipf_trace(random.Random(SEED), PHASE_REQUESTS) lru, lfu = LRUCache(CAPACITY), LFUCache(CAPACITY) assert replay(lru, trace) == 6389 assert replay(lfu, trace) == 8622 def test_the_shift_collapses_lfu_and_not_lru(): """Section 6.2: the headline. Same trace, same capacity, one shift.""" phase1, phase2 = two_phase_traces() lru, lfu = LRUCache(CAPACITY), LFUCache(CAPACITY) assert replay(lru, phase1) == 14789 # 73.94% assert replay(lfu, phase1) == 17442 # 87.21% — LFU ahead by 13 points assert replay(lru, phase2) == 14864 # 74.32% — unmoved assert replay(lfu, phase2) == 831 # 4.16% — off a cliff def test_lfu_holds_nineteen_frozen_slots_through_the_shift(): """Section 6.3: 19 slots never move; every eviction hits the 20th.""" phase1, phase2 = two_phase_traces() lfu = LFUCache(CAPACITY) replay(lfu, phase1) frozen = {k for k, c in lfu.counts.items() if c > 1} assert len(frozen) == 19 evictions_before = lfu.evictions replay(lfu, phase2) assert lfu.evictions - evictions_before == 19169 assert frozen <= set(lfu.values) # not one of them was evicted assert min(lfu.counts[k] for k in frozen) == 853 def test_a_sequential_scan_takes_lru_to_zero(): """Section 6.5: one key more than the cache holds, and LRU never hits.""" assert replay(LRUCache(100), scan_trace(100, 2000)) == 1900 # 95.00% assert replay(LRUCache(100), scan_trace(101, 2000)) == 0 # 0.00% assert replay(LFUCache(100), scan_trace(101, 2000)) == 0 # LFU too def test_neither_cache_ever_exceeds_its_capacity(): trace = zipf_trace(random.Random(SEED), 5000) for cache in (LRUCache(7), LFUCache(7)): for key in trace: if cache.get(key) is None: cache.put(key, 1) assert len(cache.keys()) <= 7 assert len(cache.keys()) == 7 TESTS = [ test_lru_evicts_the_tail_not_the_oldest_insert, test_lru_get_reorders_the_list, test_lru_links_stay_consistent_under_churn, test_lfu_keeps_the_frequently_used_key, test_lfu_breaks_count_ties_by_arrival_order, test_lfu_min_count_returns_to_one_after_an_insert, test_lfu_wins_on_a_stationary_zipf_trace, test_the_shift_collapses_lfu_and_not_lru, test_lfu_holds_nineteen_frozen_slots_through_the_shift, test_a_sequential_scan_takes_lru_to_zero, test_neither_cache_ever_exceeds_its_capacity, ] if __name__ == "__main__": failed = 0 for test in TESTS: try: test() except AssertionError as exc: failed += 1 print(f"FAIL {test.__name__}: {exc}") else: print(f"PASS {test.__name__}") if failed: print(f"\n{failed} of {len(TESTS)} tests FAILED") raise SystemExit(1) print(f"\nAll {len(TESTS)} tests PASSED")