There's Treasure Everywhere
summary
Shows concrete optimizations and measured speedups: using a sentinel at the end for linear search yields about 20–60% faster floating‑point finds; planting a vacancy hole for quicksort partition reduces overhead and saves 3–25% on partitioning (and speeds up sort accordingly); a reworked deterministic selection (median‑of‑medians with cross‑layout, repeated‑step groups and adaptive bias) cuts work and outperforms standard heuristics by up to ~70% in benchmarks generated during the slide build.
AI-written summary · about
chapters (34)
- 0:00Interview
- 4:41Efficiency
- 7:12Find Routine
- 10:24Clean Up
- 11:54CC 2016
- 15:14Partition
- 16:23Baseline Partition
- 18:51Partition Function
- 21:34Sentinel Function
- 23:39Overhead
- 24:05Center in the Middle
- 24:56Center at Both Ends
- 28:01Prelude
- 28:53Programming
- 29:16Half Swap
- 29:59Core
- 30:52Time
- 31:44Research
- 33:49Sentinels
- 39:36Cherrypicking
- 41:56QuickSelect
- 43:23Complexity of QuickSelect
- 43:47QuickSelect Example
- 44:50QuickSelect Techniques
- 47:46Media of Medians
- 50:22Classic Implementation
- 54:45Primitive Implementation
- 55:22Faster Implementation
- 55:46Optimized
- 56:03Section Title
- 56:13Indirect Rights
- 56:46Key Idea
- 57:09Ferrari
- 58:00Better layout
