What is the best way to efficiently extract a small random subset of a large enumerable?

Question

What is the best way to grab n items from an IEnumerable<T> in random order?

I'm writing a store API and need to provide a small set of random items from a sometimes huge enumeration of items. The underlying enumerable is sometimes an array, and sometimes a lazy evaluated filter of said array.

Since I'm just grabbing a proportionally small number of items from the enumerations, it is better to use some sort of repeatedly random index into the enumeration and dupe check every time rather than randomly sort the entire list using an existing algorithm and grab top x, right?

Any better ideas?

score 1 · Answer 1 · answered Jun 08 '11 at 07:17

Here's another idea:

using System;
using System.Collections.Generic;
using System.Linq;

namespace RandomElements
{
    class Program
    {
        static IEnumerable<int> GetRandomElements(IEnumerable<int> source, int count)
        {
            var random = new Random();
            var length = source.Count();
            var enumerator = source.GetEnumerator();

            if (length < count)
            {
                throw new InvalidOperationException("Seriously?");
            }

            while (count > 0)
            {
                const int bias = 5;
                var next = random.Next((length / bias) - count - bias) + 1; // To make sure we don't starve.
                length -= next;

                while (next > 0)
                {
                    if (!enumerator.MoveNext())
                    {
                        throw new InvalidOperationException("What, we starved out?");
                    }

                    --next;
                }

                yield return enumerator.Current;

                --count;
            }
        }

        static void Main(string[] args)
        {
            var sequence = Enumerable.Range(1, 100);
            var random = GetRandomElements(sequence, 10);

            random.ToList().ForEach(Console.WriteLine);
        }
    }
}

It only needs to go through the enumeration once (if you pass in an ICollection, that is, otherwise it needs to know the length). This might be useful if it's expensive to traverse the enumeration or copy all the elements or whatever.

I'm not a statistician or mathematician or magician, so don't hold it against me, but I found that without the 'bias' introduced at line 22 I felt it sort of wanted to pick more from the rear end of the sequence. Perhaps someone could tweak the probabilities more? If enumerating really is expensive, you could make it bias more towards the front.

Comments are welcome.

score 1 · Answer 2 · edited May 23 '17 at 12:12

1

In another answer I provided a way of returning a single random element from a sequence, using just a single pass.

I suspect this could be adjusted reasonably easily to use a circular buffer and select a random sequence of a given size, but you'd have to be fairly careful to get the probabilities balanced.

edited May 23 '17 at 12:12

Community

1
1

answered Mar 30 '09 at 14:09

Jon Skeet

1,421,763
867
9,128
9,194

score 0 · Answer 3 · answered Mar 30 '09 at 14:26

If you use Knuthe Shuffle, it is possible to do a random shuffle on just part of the list. So, it is not necessary to sort an entire list just to get n random items. I do not know if this can be done efficiently within your constraints since you'll still need to convert what you are grabbing into a list before you can apply the algorithm.

In essence, the strategy is to grab a random item, swap it with the first item of the list. The next time you need a random element, skip the first one.

score 0 · Accepted Answer · answered Mar 30 '09 at 14:29

0

If you know the number of items in advance, it's fairly trivial to calculate n random numbers within that range, and then grab those with these indexes.

answered Mar 30 '09 at 14:29

Dave Van den Eynde

17,020
7
59
90

As the OP says, you'd also have to make sure you don't get the same element twice. – Greg Smalter Jun 07 '11 at 15:29
That's pretty trivial, I think. Since only a small number of items are selected, you can test if you've already seen that particular random number and choose another one (or simply take the first non-chosen from that position). – Dave Van den Eynde Jun 08 '11 at 06:52

What is the best way to efficiently extract a small random subset of a large enumerable?

4 Answers4