You can sometimes put all the randomness in one part of the algorithm, even. Like shuffling before a naive quicksort.
In practice that's often even easier to understand (and debug!) than algorithms that keep making random choices as they run.
Shuffling and sorting are two humble but powerful building blocks of many algorithms. Both distributed and sequential.
In the example of what I did at Goldman, the core of the problem was essentially a souped up multi-dimensional bin packing problem. The big insight was that the typical distribution of our input data, random assignments had a high enough chance of being good, so we didn't need to keep track of everything in k-d-trees.
(k-d-trees are also awesome. And I even implemented randomized k-d-treaps at first, before I hit on an even simpler solution.)
You can sometimes put all the randomness in one part of the algorithm, even. Like shuffling before a naive quicksort.
In practice that's often even easier to understand (and debug!) than algorithms that keep making random choices as they run.
Shuffling and sorting are two humble but powerful building blocks of many algorithms. Both distributed and sequential.
In the example of what I did at Goldman, the core of the problem was essentially a souped up multi-dimensional bin packing problem. The big insight was that the typical distribution of our input data, random assignments had a high enough chance of being good, so we didn't need to keep track of everything in k-d-trees.
(k-d-trees are also awesome. And I even implemented randomized k-d-treaps at first, before I hit on an even simpler solution.)