Reservoir sampling is a statistical technique used to randomly select a finite number of elements from a population. The elements are chosen such that each element has an equal probability of being selected. This technique is often used when it is impractical to select a random sample of elements from a very large population.
To do reservoir sampling, you first need to decide how many items you want in your sample. This number is called the size of the reservoir. Once you have the size of the reservoir, you can fill it by selecting items from the population at random.
The code is beautifully simple:
for i = k to population.length-1
j = random integer between 0 and i, inclusive
if j < k
reservoir[j] = population[i]
return reservoir
Reservoir sampling is really cool - a slightly optimized version (algorithm L) let's you skip over every record that will not be sampled and it is still pretty simple. If your records are fixed size this can be an awesome speedup.
(* S has items to sample, R will contain the result )
ReservoirSample(S[1..n], R[1..k])
// fill the reservoir array
for i = 1 to k
R[i] := S[i]
(* random() generates a uniform (0,1) random number *)
W := exp(log(random())/k)
while i <= n
i := i + floor(log(random())/log(1-W)) + 1
if i <= n
(* replace a random item of the reservoir with item i *)
R[randomInteger(1,k)] := S[i] // random index between 1 and k, inclusive
W := W * exp(log(random())/k)
Indeed! Funny enough, I rewrote that article a few years ago, it previously contained an approximation of something like Algorithm L that some person with a blog came up with, having no idea that an even simpler and provably correct algorithm was published as early as 1994 :) Though others have improved the article a lot since then, adding explanations for how/why it works. Couldn't be happier to see it cited in this list!
I was going to mention it too! The really cool thing about reservoir sampling is that it can be done "online" (ie process input incrementally) which makes it super useful when you want to compute statistical properties of something in the field without blowing up your cpu and memory.
For example, let's say I have a server serving queries. I want to measure min/max/avg/stdev/99p you name it. You can do it cheaply with reservoir sampling, without having to save all data points.
To do reservoir sampling, you first need to decide how many items you want in your sample. This number is called the size of the reservoir. Once you have the size of the reservoir, you can fill it by selecting items from the population at random.
The code is beautifully simple: