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