缓存多留一个位置，为什么反而要重新读取更多次？

"""FIFO capacity anomaly and exact LRU; pure deterministic teaching models."""
import itertools
import json
from collections import deque


def simulate(references, capacity, policy):
    references = tuple(references)  # Validate and replay the same input, even for an iterator.
    if type(capacity) is not int or not 1 <= capacity <= 64:
        raise ValueError("capacity must be an integer from 1 to 64")
    if policy not in ("FIFO", "LRU"):
        raise ValueError("policy must be FIFO or LRU")
    if any(type(page) is not int or page < 0 for page in references):
        raise ValueError("page identifiers must be nonnegative integers")
    queue = deque()  # Oldest insertion (FIFO) or least recent access (LRU).
    rows = []
    for page in references:
        hit = page in queue
        evicted = None
        if hit:
            if policy == "LRU":
                queue.remove(page)
                queue.append(page)
        else:
            if len(queue) == capacity:
                evicted = queue.popleft()
            queue.append(page)
        rows.append({"page": page, "hit": hit, "evicted": evicted,
                     "cache": list(queue)})
    return {"misses": sum(not row["hit"] for row in rows), "rows": rows}


def timestamp_reference(references, capacity, policy):
    # Independent oracle: stamps and minimum selection, no eviction queue.
    stamps = {}
    rows = []
    for step, page in enumerate(references):
        hit = page in stamps
        evicted = None
        if not hit:
            if len(stamps) == capacity:
                evicted = min(stamps, key=stamps.get)
                del stamps[evicted]
            stamps[page] = step
        elif policy == "LRU":
            stamps[page] = step
        rows.append({"page": page, "hit": hit, "evicted": evicted,
                     "cache": sorted(stamps, key=stamps.get)})
    return {"misses": sum(not row["hit"] for row in rows), "rows": rows}


def main():
    checks = 0

    def check(condition):
        nonlocal checks
        if not condition:
            raise AssertionError("cache check failed")
        checks += 1

    refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
    fifo = {c: simulate(refs, c, "FIFO") for c in (3, 4)}
    lru = {c: simulate(refs, c, "LRU") for c in (3, 4)}
    check([fifo[c]["misses"] for c in (3, 4)] == [9, 10])
    check([lru[c]["misses"] for c in (3, 4)] == [10, 8])
    violation = next(i + 1 for i, (small, large) in
                     enumerate(zip(fifo[3]["rows"], fifo[4]["rows"]))
                     if not set(small["cache"]) <= set(large["cache"]))
    check(violation == 7)
    check(simulate([2, 2, 2], 1, "FIFO")["misses"] == 1)
    check(simulate([], 1, "LRU")["misses"] == 0)
    check(simulate(refs, 5, "FIFO")["misses"] == len(set(refs)))
    check(simulate(iter([2, 2, 2]), 1, "FIFO")["misses"] == 1)

    sequences = 0
    for length in range(7):
        for seq in itertools.product(range(3), repeat=length):
            sequences += 1
            for policy in ("FIFO", "LRU"):
                for capacity in range(1, 5):
                    check(simulate(seq, capacity, policy) ==
                          timestamp_reference(seq, capacity, policy))
            lru_runs = [simulate(seq, c, "LRU") for c in range(1, 5)]
            for small, large in zip(lru_runs, lru_runs[1:]):
                check(all(set(a["cache"]) <= set(b["cache"])
                          for a, b in zip(small["rows"], large["rows"])))
    for args in [([], 0, "FIFO"), ([], True, "FIFO"), ([], 1, "random"),
                 ([True], 1, "FIFO"), ([-1], 1, "LRU")]:
        try:
            simulate(*args)
        except ValueError:
            check(True)
        else:
            raise AssertionError("invalid input accepted")

    paired_trace = []
    for step, (a, b) in enumerate(zip(fifo[3]["rows"], fifo[4]["rows"]), 1):
        paired_trace.append({"step": step, "page": a["page"],
                             "FIFO3": {k: a[k] for k in ("hit", "evicted", "cache")},
                             "FIFO4": {k: b[k] for k in ("hit", "evicted", "cache")}})
    print(json.dumps({"checks_passed": checks, "small_sequences": sequences,
                      "FIFO_misses_3_4": [9, 10], "LRU_misses_3_4": [10, 8],
                      "first_FIFO_non_inclusion_step": violation,
                      "paired_trace": paired_trace,
                      "scope": "equal-sized pages; empty caches; no TTL, prefetch, bytes or real OS faults"},
                     ensure_ascii=False, indent=2))


if __name__ == "__main__":
    main()