Reservior Sampling

Problem

Take k elements at random from a stream of unknown or infinite or unknown length n in O(n)

Solution

1. Fill up a reserviour of size k using the first k readings from the stream
2. Read the next element
   • If our reservoir population was truely random, the chance of this item being in the reservoir would be k/n.
   • So we roll the dice and if Rand(1) < k/n we add this item to the reservoir and remove and existing item at random.
3. Continue until the end of the stream is reached or you get board.

Note: Since we replace a value at random, the order of samples in the reservoir is unlikely to match the order of samples in the stream. In cases where this matters it is a simple matter to store the current value of n with the sample.

Code

    class ReserviorSampling<T>
    {
        private int samplesReadSoFar = 0;
        private Random r = new Random();
        public T[] Samples;
        public int SamplesWanted { get; private set; }
 
        public ReserviorSampling(int samplesWanted)
        {
            this.Samples = new T[samplesWanted];
            this.SamplesWanted = samplesWanted;
        }
 
        public void Add(T sample)
        {
            if (samplesReadSoFar < this.SamplesWanted)
            {
                this.Samples[this.samplesReadSoFar] = sample;
            }
            else if (r.NextDouble() < (this.SamplesWanted / (double) this.samplesReadSoFar))
            {
                this.Samples[r.Next(this.SamplesWanted)] = sample;
            }
            this.samplesReadSoFar++;
        }
    }