Streaming statistics in bounded memory.
Summarize a firehose you can't fit in RAM — running moments, a uniform
sample, approximate frequencies, and heavy hitters — each in a single pass.
Sometimes the data doesn't fit in memory — a log firehose, a clickstream, a sensor feed. You still want the mean, a representative sample, the most frequent items, an estimate of how often this key showed up. The textbook answers are a small family of single-pass, bounded-memory algorithms, and tally is a clean, dependency-free, well-tested implementation of the essential four.
pip install tally-streamingZero runtime dependencies — pure standard library.
from tally import RunningStats, ReservoirSampler, CountMinSketch, HeavyHitters
stats = RunningStats().update(stream_of_numbers) # mean / variance / std, O(1)
stats.mean, stats.std
sample = ReservoirSampler(1000, seed=0) # uniform sample, never > 1000 kept
for x in huge_stream: sample.push(x)
freq = CountMinSketch.from_error(epsilon=1e-3, delta=0.01)
for key in huge_stream: freq.add(key)
freq["alpha"] # approximate count, never an underestimate
hot = HeavyHitters(k=20).update(huge_stream) # frequent items in 19 counters
hot.above(0.05) # everything over 5% of the streamOr from the terminal:
seq 1 1000000 | tally stats # n=1000000 mean=500000.5 std=288675 ...
cat access.log | tally top -k 10 # the 10 most frequent lines, in bounded memory| Structure | Algorithm | Guarantee |
|---|---|---|
RunningStats |
Welford online mean/variance | exact to floating-point, numerically stable, mergeable |
ReservoirSampler |
Vitter's Algorithm R | every item has exactly k/N chance of being kept |
CountMinSketch |
Cormode–Muthukrishnan | never underestimates; overestimate ≤ ε·N w.p. 1−δ |
HeavyHitters |
Misra–Gries | every item with freq > N/k is found; counts within N/k |
One million items (plus 200k numbers), streamed in a single pass and compared to the exact answer:
| structure | result | memory |
|---|---|---|
| RunningStats (Welford) | mean error 2.5 × 10⁻¹³, std error 3.7 × 10⁻¹⁴ | O(1) — 4 floats |
| Count-Min Sketch | max heavy-hitter relative error 0.021% | 135,915 cells vs 99,763 distinct keys |
| Misra-Gries heavy hitters | all heavy items recovered | 19 counters |
| Reservoir sample | uniform 1,000-item sample of 1,000,000 | 1,000 items |
python benchmarks/bench.py # reproduce (deterministic)The test suite verifies each structure against the exact computation — Welford
vs statistics, Count-Min's no-underestimate invariant, Misra-Gries's
no-false-negative guarantee, and reservoir uniformity across thousands of trials.
CountMinSketchandHeavyHittersuse deterministic hashing (blake2b), so results are reproducible across runs and processes — unlikehash(), which is salted per process.HeavyHitterscounts are underestimates (by at most N/k), so filter by membership for recall; a cheap second pass makes the counts exact if needed.
make install # pip install -e ".[dev]"
make test # 15 tests, each checked against the exact answer
make lint # ruff
make bench # regenerate benchmarks/results.mdMIT © Hritik Datta