Reservoir Sampling of an enumerable collection of unknown size

Question

I have an enumerable source for which I do not know how big it is. I want to select a random element from it, without having to hold the whole collection in memory and with uniform distribution. I read about the reservoir sampling algorithm, and created a simple implementation for the very basic case where the reservoir size is 1, which is what I want.

Basically the idea is that if an item appears in position n starting by 1, if a random roll returns less than 1/n I pick that value as the current selected value.

static T Random<T>(IEnumerable<T> source, Random random)
{
    using var e = source.GetEnumerator();
    if(!e.MoveNext())
        return default;
    var result = e.Current;
    var count = 1;
    while(e.MoveNext())
    {
        if(random.NextDouble() < 1.0 / ++count)
            result = e.Current;
    }
    
    return result;
}

I created a demo project and the results seems to add up.

https://dotnetfiddle.net/0iXEck

public static void Main()
{
    var size = 1000;
    var tries = size * 100;
    var random = new Random();
    var array = Enumerable.Range(0, size).ToArray();
    var histogram = array.ToDictionary(k => k, v => 0);
    for(var i=0; i<tries; i++)
        histogram[Random(array, random)]++;
    foreach(var kv in histogram.OrderBy(kv => kv.Key))
        Console.WriteLine($"{kv.Key,5}: {kv.Value}");
}

I wonder if am I missing anything because probability knowledge is not my strongest point. Is this still "reservoir sampling algorithm" or does it have another name?

Answer 1

Let me try another answer.

Background info: Wikipedia Reservoir Sampling.

The intro header to the Wikipedia link states:

The size of the population n is not known to the algorithm and is typically too large for all n items to fit into main memory.

But consider you have a dictionary to hold the results for all n items in your main memory. And each example they provide has it returning a complete array, so it all has to fit into memory somehow.

You could make your life easier if your method accepted an IList<T> since that would return a known Count. Consider that each individual call to your method will enumerate over EACH element in the collection. Since you pass in a 1000 element array, all 1000 elements are enumerated for one call, and you make 100 calls. I am just saying after the first call has been made, the size of the collection is no longer unknown. Rather it is not remembered between invocations.

But that is not what you asked for. My answer continues to with IEnumerable<T> of unknown length.

Typically, one does not pass in the Random instance, but rather relies upon the method to have one handy.

The method name Random<T> is a poor name producing much confusion with the Random class. I suggest it be GetReservoirSample<T>.

For C#, the CodeReview community strongly supports uses braces to avoid one-liners.

There is no reason to OrderBy Key on histogram since it was created in Key order.

A quick reworking of your method, which includes Random as an optional parameter, would become:

private static Random _random = new Random();

public static T GetReservoirSample1<T>(IEnumerable<T> source, Random random = null)
{
    T result = default;
    int count = 0;
    if (random == null)
    {
        random = _random;
    }
    IEnumerator<T> e = source.GetEnumerator();
    // This enumerates over the entire collection!!!
    while (e.MoveNext())
    {
        if (random.NextDouble() < (1.0 / ++count))
        {
            result = e.Current;
        }
    }
    return result;
}

But that can be simplified by getting rid of the Random parameter. And since you are iterating over all elements, there is no need for the enumerator. You may use an foreach instead yielding smaller code.

public static T GetReservoirSample2<T>(IEnumerable<T> source)
{
    T result = default;
    int count = 0;
    // This enumerates over the entire collection!!!
    foreach (var element in source)
    {
        if (_random.NextDouble() < (1.0 / ++count))
        {
            result = element;
        }
    }
    return result;
}

IList versus IEnumerable

Finally, if you ever decide to change source to be an IList<T>, there is this version:

static T GetReservoirSample3<T>(IList<T> source)
{
    T result = source.Count > 0 ? source[0] : default;
    // This enumerates over the entire collection MINUS ONE!!!
    for (int i = 1;  i < source.Count; i++)
    {
        if (_random.NextDouble() < (1.0 / (i + 1.0)))
        {
            result = source[i];
        }

    }
    return result;
}

UPDATED

In my original example using IList<T>, there is no performance benefit. Each example must enumerate over the full collection. However, with a IList you can get a performance boost. Essentially, your method remembers the last element that satisfies the condition but it must continue to enumerate over the remainder of the collection.

With a list, you can process the collection backwards and immediately return on the first item that satisfies the condition:

static T GetReservoirSample3B<T>(IList<T> source)
{
    for (int i = source.Count - 1; i > 0; i--)
    {
        if (_random.NextDouble() < (1.0 / (i + 1.0)))
        {
            return source[i];
        }

    }
    return source[0];
}

Also, I wanted to see the min and max values, so I altered Main for my own purposes. I share it here:

public static void Main()
{
    var size = 1000;
    var tries = size * 100;
    var array = Enumerable.Range(0, size).ToArray();
    var histogram = array.ToDictionary(k => k, v => 0);
    var random = new Random();
    for (var i = 0; i < tries; i++)
    {
        histogram[GetReservoirSample3B(array)]++;
    }
    var min = int.MaxValue;
    var max = int.MinValue;
    foreach (var kv in histogram) 
    {
        if (kv.Value < min)
        {
            min = kv.Value;
        }
        if (kv.Value > max)
        {
            max = kv.Value;
        }
    }
    foreach (var kv in histogram) 
    {
        var extra = (kv.Value == min) ? "\t** MININUM ** " : (kv.Value == max) ? "\t** MAXIMUM **" : "";
        Console.WriteLine($"{kv.Key,5}: {kv.Value}{extra}");
    }
}

All that said, I do not know if you are correctly implementing a reservoir sampling. From what I read, it expects you to return a sample subset of k elements where k is less than or equal to the source collection size of n. Since you are returning a single element, that is for k == 1, then this produces the same distribution as:

static T GetReservoirSample3C<T>(IList<T> source) => source[_random.Next(source.Count)];