Series
Algorithms
The algorithms that run over the structures. Sorting, searching, graphs, dynamic programming, string matching, randomised methods and compression, one at a time: what the mechanism actually is, where the cost goes, the shape of problem it fits, when to reach for something else, and the Go to write it. The companion to Data Structures, which covers what holds the data. Part of Under the Hood.
What Makes an Algorithm Fast
Big-O counts one operation and discards everything else, which is why two O(1) reads from the same array measured 0.66 and 193 nanoseconds: the same order, 294 times apart. This opens the Algorithms group by setting out what the notation claims and what it leaves to the machine, with the constant factor, the cache hierarchy, branch prediction and allocation measured rather than guessed. Amortised analysis gets the dynamic array as its worked case: a million pushes copy 1,048,575 elements under doubling and 499,999,500,000 under growth by one, and moving the shrink threshold from a quarter of the capacity to half turns a 29 nanosecond push-and-pop into 9.4 microseconds. Every figure here came out of Go's testing.B on one machine.
Coming soon