Выбрать из списка 400 случайных элементов

#c_sharp #list #случайные_числа

Есть список:

List list = new List();


Его count 10 000. Нужно выбрать 400 случайных (рандомных) элементов этого списка
и поместить их в новый список:

List listNew = new List();


Если использовать r.Next(0, list.Count - 1), то есть вероятность того, что рандом
может выбрать один и тот же элемент дважды. Как этого избежать и выбрать 400 рандмных
уникальных элементов?
    

Ответы

Ответ 1

На первый взгляд, это классическая задача на алгоритм Reservoir Sampling. Задача
решается за один последовательный проход по списку, и при этом для достижения равновероятной
выборки вам даже не надо заранее знать количества элементов в списке. При этом не нужно
прибегать к ужасной порочной практике "проб и ошибок" (проверка "уже брали - еще не
брали"), которую часто предлагают использовать при составлении наивных алгоритмов для
решения данной задачи.

Алгоритм таков:


Заводим массив из 400 элементов и заполняем его первыми 400 элементами списка.
Читаем в цикле дальнейшие элементы списка (с 401-го и далее):  

2.1. Берем i-тый элемент из списка и с вероятностью 400/i принимаем решение сохранить
этот элемент в нашей выборке. Если принято решение "не сохранять", то просто пропускаем
его.  

2.2. Если принято решение сохранить элемент, сохраняем его в случайную позицию в
нашем массиве (выбросив оттуда предыдущий элемент).


Пройдя таким циклом весь список до конца, мы получим 400 равновероятно выбранных
элементов списка.

Как видите, для эффективной реализации выбранные 400 элементов желательно в процессе
работы алгоритма хранить в массиве, а не в списке. Тут уже думайте сами, как лучше
поступить: завести изначально массив, а затем скопировать выбранные элементы в список,
или сразу хранить их в списке, пожертвовав эффективностью прямого доступа при замене
на шаге 2.2.



Однако если ваш исходный список предоставляет возможность эффективного прямого доступа
(см. комментарий @Андрей NOP), то вариант "проб и ошибок" будет вполне жизнеспособным
и даже более эффективным, так как 400 намного меньше 10000.


Ответ 2

Если производительность некритична перемешиваем весь список

Неоптимальный и грубый, но достаточно прямолинейный подход: перемешать весь список
в случайном порядке и выбрать первые 400:

var random = new Random();
var listNew = list.OrderBy(s=> random.Next()).Take(400).ToList();


Неоптимальный т.к. будет сортировать весь список.
Грубый т.к. коллизии случайных чисел приведут к тому, что попадание первых по порядку
элементов будет на какую долю выше.

Поход для малой выборки: отбираем уникальные индексы

Напишем метод, который генерирует бесконечную последовательность случайных индексов:

private static Random random;

public static IEnumerable RandomNumbers(int maxValue)
    {
        while (true)
        {
            yield return random.Next(maxValue);
        }
    } 


С помощью метода получим 400 уникальных индексов и отберем элементы:

var uniqueIndices = RandomNumbers(list.Count).Distinct().Take(400);
var listNew = uniqueIndices.Select(i => list[i]).ToList();


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