FA-73141 / Probabilistic sketches / Open access
Space-Saving heavy hitters: equal counts listed in insertion order · case 01
Top-k reports with tied counts are ordered inconsistently between runs with different arrival orders.
ROOT CAUSE
Rows are sorted by count only, leaving ties in dictionary insertion order.
VERIFIED REPAIR
Sort by count descending and then by item ascending.
Unsuccessful approach: Reversing a full ascending sort also reverses the item tie-break.
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] = [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])
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 | [[['y', 3, 2], ['w', 3, 2]], ['w', 'y']] | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | Failed |
| equal counts different recency | [[['r', 3, 2], ['q', 3, 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 / 8b57c024e28720e7e85b8ca6f537119edbb271853b99fbc85dc04248f73c79ef
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 + 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]), reverse=True)
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 | [[['d', 3, 2], ['c', 3, 2]], []] | [[['c', 3, 2], ['d', 3, 2]], []] | Failed |
| boundary threshold | [[['c', 4, 3], ['b', 3, 0]], []] | [[['c', 4, 3], ['b', 3, 0]], []] | Passed |
| refresh on hit | [[['y', 3, 2], ['w', 3, 2]], ['w', 'y']] | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | Failed |
| equal counts different recency | [[['r', 3, 2], ['q', 3, 2]], []] | [[['q', 3, 2], ['r', 3, 2]], []] | Failed |
| no eviction | [[['r', 2, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']] | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | Failed |
SHA-256 / 857f5a9f9b59935d32c130ef484be22646035d5a236cb05220bbc0fec0db7fb7
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.803326+00:00.
Case digest / 30e887fa06f43251cf8c07da839217f4415c67ad6ac8d31f6429cd22760ebbea