4

Есть список:

List<string> list = new List<string>();

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

List<string> listNew = new List<string>();

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

4
  • 400 из 10 000 - не так уж много, просто запоминайте индексы уже выбранных элементов в Hashset и при выборе следующего проверяйте чтобы его не было в Hashset 14 июн 2018 в 6:04
  • Заводите hashset и складываете а него рандомы, пока он не станет содержать 400 элементов. Второй вариант — заводите список на 10000 элементов, выбираете в нем случайный элемент и удаляем его, выбираем следующий случайный и тоже удаляем, и так 400 раз. В вашем случае скорее всего первый вариант лучше
    – tym32167
    14 июн 2018 в 6:06
  • Удалил старую чушь, сделайте как было предложено, лучше случайно генерировать позицию и проверять, не выбрана ли она ранее через тот же HashSet, если производительность не критична. 14 июн 2018 в 6:13
  • 1

2 ответа 2

4

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

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

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

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

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

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

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


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

2
  • 1
    Коллекция List<> в .Net это тот же массив с константным доступом по индексу (просто со спрятанным от пользователя изменением вместимости). Я это про "желательно ... хранить в массиве, а не в списке", уход от List<> к массиву ничего ровным счетом не даст 14 июн 2018 в 6:27
  • Пример на C#: ideone.com/HlfyON Хорошо было бы показать в ответе вывод вероятности для i-го элемента. Понимаю, что это можно найти по ссылкам, но здесь было бы нагляднее. 14 июн 2018 в 7:05
3

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

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

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

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

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

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

private static Random random;

public static IEnumerable<int> 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 элементов, этот метод будет неоптимален ввиду частых совпадений случайных чисел.

4
  • 1
    Следует заметить, что чем большее число элементов мы выбираем из входного списка, тем дольше будет выбираться каждый следующий элемент из-за частого совпадения сгенерированных индексов с уже использованными. В этом плане алгоритм из соседнего ответа гораздо более оптимален. 14 июн 2018 в 6:32
  • @АндрейNOP Точно, спасибо! Уточню в ответе. 14 июн 2018 в 6:35
  • 1
    @defaultlocale А в случае 9999 элементов из 10000 не проще случайно выбрать ненужный индекс?
    – John
    14 июн 2018 в 6:41
  • @John Проще, но это дополнительная логика. 9999 — крайний пример, коллизии начнут оказывать влияние и на меньших выборках. В любом случае Ant уже показал универсальный O(n) алгоритм. 14 июн 2018 в 6:45

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.