FA-73116 / Probabilistic sketches / Open access
Space-Saving heavy hitters: newcomer restarts at one · case 01
Evicted mass disappears, so counts underestimate and the overestimate-only property is lost.
ROOT CAUSE
The replacement entry starts at count 1 instead of inheriting the victim count plus one.
VERIFIED REPAIR
Set the new count to victim count + 1.
Unsuccessful approach: Inheriting the victim count without adding one ignores the newcomer's own occurrence.
Case contract
Input {k, stream, phi=[num, den]}. Keep k entries [count, error, last-touch tick]. A hit increments count and refreshes the tick. A miss with free space inserts [1, 0, tick]. Otherwise evict the entry with the smallest count, ties broken by the oldest tick, and insert the newcomer with count = victim count + 1 and error = victim count. Return [rows sorted by count descending then item, sorted items whose guaranteed count (count - error) exceeds phi * stream length].
Why this case matters
Top-k dashboards and abuse detectors use Space-Saving because its per-item error bound lets them separate guaranteed heavy hitters from possible ones.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
S = {}
tick = 0
for item in x['stream']:
tick += 1
if item in S:
S[item][0] += 1
S[item][2] = tick
elif len(S) < k:
S[item] = [1, 0, tick]
else:
victim = min(S, key=lambda key: (S[key][0], S[key][2]))
cnt = S.pop(victim)[0]
S[item] = [1, cnt, tick]
Ntot = len(x['stream'])
num, den = x['phi']
rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))
guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den > num * Ntot)
return [rows, guaranteed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},
[[['a', 9, 3], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},
[[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},
[[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},
[[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},
[[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},
[[['a', 10, 4], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},
[[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},
[[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},
[[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},
[[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'a',
'b',
'b',
'b',
'a',
'e',
'a',
'a',
'a',
'b',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['d',
'b',
'a',
'a',
'a',
'e',
'c',
'a',
'f',
'c',
'a',
'e',
'b',
'a',
'a',
'a',
'a']},
[[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'd',
'b',
'c',
'c',
'c',
'a',
'd',
'c',
'b',
'd',
'b',
'a',
'b']},
[[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'a',
'c',
'c',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'c',
'd',
'a']},
[[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},
[[['c', 3, 2], ['a', 2, 0]], ['a']]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},
[[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['d',
'a',
'c',
'a',
'b',
'a',
'b',
'a',
'e',
'a',
'a',
'a',
'd',
'c',
'b',
'a',
'b',
'a']},
[[['a', 9, 7], ['b', 9, 7]], []]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'f',
'f',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'a',
'a',
'b']},
[[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'c',
'c',
'e',
'a',
'f',
'c',
'c',
'e',
'd',
'f',
'b',
'a',
'a',
'c',
'b',
'b']},
[[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['e',
'a',
'a',
'a',
'a',
'b',
'a',
'd',
'e',
'a',
'd',
'a',
'g',
'a',
'c',
'g',
'c',
'b']},
[[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},
[[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'a',
'a',
'b',
'a',
'a',
'c',
'a',
'e',
'a',
'a',
'a',
'a',
'a',
'a',
'd',
'c']},
[[['a', 13, 0], ['c', 6, 5]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'b',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'b',
'a',
'f',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'a',
'a',
'c',
'f',
'f',
'a',
'a',
'a',
'b',
'b',
'b',
'b',
'a',
'd',
'a',
'a']},
[[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b',
'c',
'a',
'b',
'a',
'b',
'a',
'b',
'b',
'a',
'a',
'c',
'd',
'f',
'a',
'd',
'a',
'a',
'g']},
[[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},
[[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| skewed stream 0 k=2 | [[['a', 6, 1], ['b', 5, 0]], ['a', 'b']] | [[['a', 9, 3], ['b', 6, 4]], ['a']] | Failed |
| skewed stream 1 k=3 | [[['a', 7, 1], ['e', 2, 0], ['b', 1, 1]], ['a']] | [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']] | Failed |
| skewed stream 2 k=3 | [[['a', 8, 0], ['b', 3, 0], ['c', 1, 3]], ['a']] | [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']] | Failed |
| skewed stream 3 k=4 | [[['a', 7, 0], ['b', 5, 0], ['c', 1, 0], ['g', 1, 1]], ['a', 'b']] | [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']] | Failed |
| tie eviction by age | [[['a', 2, 0], ['d', 1, 1]], []] | [[['c', 3, 2], ['d', 3, 2]], []] | Failed |
| boundary threshold | [[['b', 3, 0], ['c', 1, 3]], []] | [[['c', 4, 3], ['b', 3, 0]], []] | Failed |
| refresh on hit | [[['x', 2, 0], ['w', 1, 1]], ['x']] | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | Failed |
| equal counts different recency | [[['p', 2, 0], ['q', 1, 1]], ['p']] | [[['q', 3, 2], ['r', 3, 2]], []] | Failed |
| no eviction | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | Passed |
SHA-256 / 529ca7f324adcd01655d2547c475d145ca5113a773aa8be8af3fc45afaf349d2
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
S = {}
tick = 0
for item in x['stream']:
tick += 1
if item in S:
S[item][0] += 1
S[item][2] = tick
elif len(S) < k:
S[item] = [1, 0, tick]
else:
victim = min(S, key=lambda key: (S[key][0], S[key][2]))
cnt = S.pop(victim)[0]
S[item] = [cnt, cnt, tick]
Ntot = len(x['stream'])
num, den = x['phi']
rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))
guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den > num * Ntot)
return [rows, guaranteed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},
[[['a', 9, 3], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},
[[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},
[[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},
[[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},
[[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},
[[['a', 10, 4], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},
[[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},
[[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},
[[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},
[[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'a',
'b',
'b',
'b',
'a',
'e',
'a',
'a',
'a',
'b',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['d',
'b',
'a',
'a',
'a',
'e',
'c',
'a',
'f',
'c',
'a',
'e',
'b',
'a',
'a',
'a',
'a']},
[[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'd',
'b',
'c',
'c',
'c',
'a',
'd',
'c',
'b',
'd',
'b',
'a',
'b']},
[[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'a',
'c',
'c',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'c',
'd',
'a']},
[[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},
[[['c', 3, 2], ['a', 2, 0]], ['a']]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},
[[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['d',
'a',
'c',
'a',
'b',
'a',
'b',
'a',
'e',
'a',
'a',
'a',
'd',
'c',
'b',
'a',
'b',
'a']},
[[['a', 9, 7], ['b', 9, 7]], []]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'f',
'f',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'a',
'a',
'b']},
[[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'c',
'c',
'e',
'a',
'f',
'c',
'c',
'e',
'd',
'f',
'b',
'a',
'a',
'c',
'b',
'b']},
[[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['e',
'a',
'a',
'a',
'a',
'b',
'a',
'd',
'e',
'a',
'd',
'a',
'g',
'a',
'c',
'g',
'c',
'b']},
[[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},
[[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'a',
'a',
'b',
'a',
'a',
'c',
'a',
'e',
'a',
'a',
'a',
'a',
'a',
'a',
'd',
'c']},
[[['a', 13, 0], ['c', 6, 5]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'b',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'b',
'a',
'f',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'a',
'a',
'c',
'f',
'f',
'a',
'a',
'a',
'b',
'b',
'b',
'b',
'a',
'd',
'a',
'a']},
[[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b',
'c',
'a',
'b',
'a',
'b',
'a',
'b',
'b',
'a',
'a',
'c',
'd',
'f',
'a',
'd',
'a',
'a',
'g']},
[[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},
[[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| skewed stream 0 k=2 | [[['a', 7, 2], ['b', 5, 0]], ['a', 'b']] | [[['a', 9, 3], ['b', 6, 4]], ['a']] | Failed |
| skewed stream 1 k=3 | [[['a', 7, 1], ['e', 2, 0], ['b', 1, 1]], ['a']] | [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']] | Failed |
| skewed stream 2 k=3 | [[['a', 8, 0], ['b', 3, 0], ['c', 3, 3]], ['a']] | [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']] | Failed |
| skewed stream 3 k=4 | [[['a', 7, 0], ['b', 5, 0], ['c', 1, 0], ['g', 1, 1]], ['a', 'b']] | [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']] | Failed |
| tie eviction by age | [[['c', 2, 2], ['d', 2, 2]], []] | [[['c', 3, 2], ['d', 3, 2]], []] | Failed |
| boundary threshold | [[['b', 3, 0], ['c', 3, 3]], []] | [[['c', 4, 3], ['b', 3, 0]], []] | Failed |
| refresh on hit | [[['x', 2, 0], ['w', 1, 1]], ['x']] | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | Failed |
| equal counts different recency | [[['q', 2, 2], ['r', 2, 2]], []] | [[['q', 3, 2], ['r', 3, 2]], []] | Failed |
| no eviction | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | Passed |
SHA-256 / ef581d58cb2eba36ac24521eae71ce09de7778a59540d5ea8f8430c878b344e7
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
S = {}
tick = 0
for item in x['stream']:
tick += 1
if item in S:
S[item][0] += 1
S[item][2] = tick
elif len(S) < k:
S[item] = [1, 0, tick]
else:
victim = min(S, key=lambda key: (S[key][0], S[key][2]))
cnt = S.pop(victim)[0]
S[item] = [cnt + 1, cnt, tick]
Ntot = len(x['stream'])
num, den = x['phi']
rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))
guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den > num * Ntot)
return [rows, guaranteed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},
[[['a', 9, 3], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},
[[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},
[[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},
[[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},
[[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},
[[['a', 10, 4], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},
[[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},
[[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},
[[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},
[[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'a',
'b',
'b',
'b',
'a',
'e',
'a',
'a',
'a',
'b',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['d',
'b',
'a',
'a',
'a',
'e',
'c',
'a',
'f',
'c',
'a',
'e',
'b',
'a',
'a',
'a',
'a']},
[[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'd',
'b',
'c',
'c',
'c',
'a',
'd',
'c',
'b',
'd',
'b',
'a',
'b']},
[[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'a',
'c',
'c',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'c',
'd',
'a']},
[[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},
[[['c', 3, 2], ['a', 2, 0]], ['a']]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},
[[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['d',
'a',
'c',
'a',
'b',
'a',
'b',
'a',
'e',
'a',
'a',
'a',
'd',
'c',
'b',
'a',
'b',
'a']},
[[['a', 9, 7], ['b', 9, 7]], []]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'f',
'f',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'a',
'a',
'b']},
[[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'c',
'c',
'e',
'a',
'f',
'c',
'c',
'e',
'd',
'f',
'b',
'a',
'a',
'c',
'b',
'b']},
[[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['e',
'a',
'a',
'a',
'a',
'b',
'a',
'd',
'e',
'a',
'd',
'a',
'g',
'a',
'c',
'g',
'c',
'b']},
[[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},
[[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'a',
'a',
'b',
'a',
'a',
'c',
'a',
'e',
'a',
'a',
'a',
'a',
'a',
'a',
'd',
'c']},
[[['a', 13, 0], ['c', 6, 5]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'b',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'b',
'a',
'f',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'a',
'a',
'c',
'f',
'f',
'a',
'a',
'a',
'b',
'b',
'b',
'b',
'a',
'd',
'a',
'a']},
[[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b',
'c',
'a',
'b',
'a',
'b',
'a',
'b',
'b',
'a',
'a',
'c',
'd',
'f',
'a',
'd',
'a',
'a',
'g']},
[[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},
[[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| skewed stream 0 k=2 | [[['a', 9, 3], ['b', 6, 4]], ['a']] | [[['a', 9, 3], ['b', 6, 4]], ['a']] | Passed |
| skewed stream 1 k=3 | [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']] | [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']] | Passed |
| skewed stream 2 k=3 | [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']] | [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']] | Passed |
| skewed stream 3 k=4 | [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']] | [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']] | Passed |
| tie eviction by age | [[['c', 3, 2], ['d', 3, 2]], []] | [[['c', 3, 2], ['d', 3, 2]], []] | Passed |
| boundary threshold | [[['c', 4, 3], ['b', 3, 0]], []] | [[['c', 4, 3], ['b', 3, 0]], []] | Passed |
| refresh on hit | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | Passed |
| equal counts different recency | [[['q', 3, 2], ['r', 3, 2]], []] | [[['q', 3, 2], ['r', 3, 2]], []] | Passed |
| no eviction | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | Passed |
SHA-256 / ba81dc8785f3eb10330a037ce768b6cd708e1eaf456538b9f35ae983bc2ec660
Verification & scope
A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:48:44.628171+00:00.
Case digest / e60e3f39b3dae675f0783d00c9c0ad3ebcaef2389447adbecec4ecbef61badbb