Fantastic Algorithms and Where To Find Them
summary
Describes concrete algorithms and what they actually guarantee: heavy hitters (Boyer‑Moore style) flags every key above an x% threshold with a single pass but generally needs a verification pass unless the implementation (gcov) checks count/weight and thus guarantees recovery for ≥75% offenders; Morris traversal does in‑order visit and safe destruction with O(1) extra space by temporarily threading predecessors and restoring them; reservoir sampling returns exactly k uniform samples from a stream using one RNG per item; HyperLogLog estimates distinct counts with error ≈1.04/√m after hashing and harmonic‑mean aggregation.
AI-written summary · about
chapters (7)
- 0:00Start
- 5:12Heavy Hitters (X=50%, Majority Vote)
- 12:05Heavy Hitters (X=1/k)
- 20:16Morris Traversal
- 34:05Reservoir Sampling
- 43:46HyperLogLog
- 54:54#include
related talks
59mBetter Algorithm Intuition
48m[a bit noisy] Optimizing Generic Algorithms
44mStories from a parallel universe
01h 07mWriting Data Parallel Algorithms on GPUs
48mReal time 101
40mRust’s approach of getting things right
01h 14mEfficiency with Algorithms, Performance with Data Structures
52mBest Practices for Concurrency