Fantastic Algorithms and Where To Find Them
summary
Describes concrete, deployable techniques: Boyer-Moore majority and its 1/k generalization for heavy hitters used to throttle DOSy callers (variant run per five-minute interval, Gcov uses a counter trick that guarantees detection at ≥75% frequency); Morris traversal for O(1) stack inorder traversal and destruction that restores tree shape by threading predecessors; reservoir sampling implemented in BigGrep’s --sample flag and running in production for four years; and HyperLogLog for approx_count_distinct with m=2048 giving ~2% error.
AI-written summary · about
chapters (9)
- 0:00Introduction to Algorithms
- 1:23Heavy Hitters Algorithm
- 8:25Frequency and Verification
- 11:42Memory Management Challenges
- 13:58Morris Traversal
- 20:41Reservoir Sampling
- 27:31HyperLogLog Introduction
- 36:01HyperLogLog Implementation
- 43:24Standard Library Algorithms
related talks
01h 01mAlgorithm Intuition (part 2 of 2)
44mWhat is your Algorithmic Core?
01h 04mBetter Code: Data Structures
01h 30mSorting Algorithms: Speed Is Found In The Minds of People
56mBeginners Guide to C++'s Best Kept Secret -- std::algorithm
59mTheory makes beautiful programs
01h 23mAlex Stepanov, Generic Programming in Cpp, and the STL
05mFinding Strings in Large Files