What is Reservoir Sampling?

Reservoir sampling is a family of randomized algorithms for choosing a simple random sample of k items from a population of unknown size n, in a single pass over the items. The size of the population n is not known to the algorithm.

Why is Reservoir Sampling useful?

It's extremely useful for sampling from very large or infinite data streams where it's impossible to store all the data in memory. It ensures that every item in the stream has an equal probability of being chosen for the sample.

Data Streams

Reservoir Sampling

A clever algorithm for selecting a random sample of `k` items from a data stream of unknown size, ensuring every item has an equal chance of being selected.

Select k Items from a Stream

This implementation of Reservoir Sampling (Algorithm R) creates a reservoir of size `k` and processes the stream, replacing elements with a decreasing probability.

                            function reservoirSample(stream, k) {
                            const reservoir = [];
                            let i = 0;
                            
                            for (const item of stream) {
                            if (i < k) {
                            reservoir.push(item);
                            } else {
                            const j = Math.floor(Math.random() * (i + 1));
                            if (j < k) {
                            reservoir[j] = item;
                            }
                            }
                            i++;
                            }
                            return reservoir;
                            }
                        

AI Coach Hint: The probability magic happens in the `else` block. For the i-th item (where i >= k), the probability of it being selected is k/i. This ensures that after processing n items, every item has a k/n probability of being in the reservoir.