Каков наилучший способ эффективного извлечения небольшого случайного подмножества большого перечислимого?

Question

Каков наилучший способ получить n элементов из IEnumerable в случайном порядке?

Я пишу API магазина и должен предоставить небольшой набор случайных предметов из иногда огромного перечня предметов. Базовое перечисляемое иногда представляет собой массив, а иногда ленивый оцененный фильтр указанного массива.

Поскольку я просто отбираю пропорционально небольшое количество элементов из перечислений, лучше использовать какой-то многократно случайный индекс в перечислении и проверять дублирование каждый раз, а не случайным образом сортировать весь список, используя существующий алгоритм и возьмите топ х, верно?

Есть идеи получше?

Answer 1

Вот еще одна идея:

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);
        }
    }
}

Перечисление нужно пройти только один раз (если вы передаете ICollection, то есть в противном случае ему нужно знать длину). Это может быть полезно, если обходить перечисление или копировать все элементы или что-либо еще дорого.

Я не статистик, не математик и не волшебник, так что не держите это против меня, но я обнаружил, что без «предвзятости», введенной в строке 22, я чувствовал, что вроде бы хотел выбрать больше из задней части последовательность. Возможно, кто-то мог бы подправить вероятности больше? Если перечисление действительно дорого, вы можете сделать его более смещенным вперед.

Комментарии приветствуются.

Answer 2

Если вы используете Knuthe Shuffle , можно сделать случайное перемешивание только для части списка. Таким образом, нет необходимости сортировать весь список только для того, чтобы получить n случайных элементов. Я не знаю, может ли это быть эффективно сделано в рамках ваших ограничений, поскольку вам все еще нужно преобразовать то, что вы захватываете, в список, прежде чем применять алгоритм.

По сути, стратегия заключается в том, чтобы захватить случайный элемент, поменять его местами с первым элементом списка. В следующий раз, когда вам понадобится случайный элемент, пропустите первый.

Answer 3

Если вы знаете количество элементов заранее, то довольно просто вычислить n случайных чисел в этом диапазоне, а затем взять их с этими индексами.

Answer 4

В другом ответе я предоставил способ возврата одного случайного элемента из последовательности, используя всего один проход.

I подозреваю это можно довольно легко настроить, чтобы использовать кольцевой буфер и выбирать случайную последовательность заданного размера, но вам нужно быть достаточно осторожным, чтобы сбалансировать вероятности.