Эффективная случайная выборка из огромного списка

Question

У меня есть файл данных с большим количеством значений (53 000 000+), и я хотел бы извлечь случайное подмножество n из этих значений (скажем, 2 000 000). Я реализовал Perl-скрипт, который вытягивает список в память, использует метод Фишера-Йейтса , чтобы перетасовать массив, и затем выводит первые значения n в перетасованном списке. Однако этот процесс тасования занимает много времени, даже на гораздо меньших тестовых наборах (50 000 значений).

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

Обновление : Судя по ответам и дальнейшим поискам, правильная терминология выглядит как "случайная выборка".

Answer 1

Прорабатывая ответ AIX выше, чтобы выбрать k из потока предметов, читайте предметы по одному.Держите первые k предметов в наборе S.

Теперь, читая m -й элемент I (m>k сейчас), сохраните его с вероятностью k/m.Если вы сохраните его, выберите элемент U случайным образом из S и замените U на I.

Доказательство того, что это дает все подмножества размера k равнымивероятность основана на индукции на m.Обратите внимание, что вам не нужно заранее знать n (общее количество предметов), и что S на каждом шаге подходит.Алгоритм является «потоковым» - он не требует хранения всех элементов или повторного прохода.

Answer 2

Не тасуйте, это излишне дорого.

Существует простой линейный алгоритм , обсуждаемый в "Programming Pearls" Джона Бентли (который, по словам Бентли, он узнал из "Полу числовых алгоритмов" Кнута ). Вместо этого используйте этот метод.

Существует несколько реализаций Perl about:

В этих двух фрагментах реализованы алгоритмы S (3.4.2) и R (3.4.2). от Кнута Искусство программирования. Первый случайным образом выбирает N предметов из массива элементов и возвращает ссылку на массив содержащий элементы. Обратите внимание, что это не обязательно будет учитывать все элементы в списке.

Второй случайным образом выбирает N элементов из файла неопределенного размера. и возвращает массив, содержащий выбранные элементы. Записи в Предполагается, что файл находится на каждой строке, а строки чтение. Для этого требуется всего 1 проход по списку. Небольшой можно использовать модификацию для использования фрагмента в ситуациях, когда N записи будут превышать ограничения памяти, однако это требует чуть более 1 прохода (/ msg, если вам нужно это объяснять)

Answer 3

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

Если вы попросите k чисел, это будет стоить вам k элементарных операций. Я сомневаюсь, что вы можете сделать намного лучше, чем это.

Answer 4

Чтение и перемешивание массива потребует большого количества ненужных перемещений данных.

Вот несколько идей:

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

Потому что я сначала подумал, что если записи не в каком-либо соответствующем порядке, то вы можете получить случайный выбор, просто рассчитав общий размер, деленный на размер выборки, а затем выбрав каждую n-ю запись. Так, например, если у вас есть 53 миллиона записей и вы хотите выбрать 2 миллиона, возьмите 53 миллиона / 2 миллиона ~ = 26, поэтому прочитайте каждую 26-ую запись.

Два: если этого недостаточно, более строгим решением было бы сгенерировать 2 миллиона случайных чисел в диапазоне от нуля до 53 миллионов без страховки дубликатов.

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

Two-B: если ваши цифры не просто примеры, а фактические значения, тогда размер вашей выборки будет большим по сравнению с общей численностью населения. В этом случае, имея достаточно памяти на современных компьютерах, вы сможете сделать это эффективно, создав массив из 53 миллионов логических значений, инициализированных как false, каждый из которых, конечно, представляет одну запись. Затем выполните цикл 2 миллиона раз. Для каждой итерации генерируйте случайное число от 0 до 53 миллионов. Проверьте соответствующее логическое значение в массиве: если оно равно false, установите для него значение true. Если это правда, сгенерируйте другое случайное число и попробуйте снова.

Три: Или, подождите, вот лучшая идея, учитывая относительно большой процент: Рассчитайте процент записей, которые вы хотите включить. Затем переберите счетчик всех записей. Для каждого сгенерируйте случайное число от 0 до 1 и сравните его с желаемым процентом. Если меньше, прочитайте эту запись и включите ее в пример. Если оно больше, пропустите запись.

Если важно получить точное количество записей выборки, вы можете пересчитать процент для каждой записи. Например - и чтобы сохранить пример простым, представим, что вы хотите 10 из 100 записей:

Вы начнете с 10/100 = .1 Итак, мы генерируем случайное число, скажем, оно приходит .04. .04 <.1, поэтому мы включаем запись # 1. </p>

Теперь мы пересчитаем процент. Мы хотим, чтобы еще 9 записей из 99 оставшихся дали 9/99 ~ = .0909. Скажем, наше случайное число равно 0,87. Это больше, поэтому мы пропускаем запись № 2.

Пересчитать снова. Нам все еще нужно 9 записей из 98 оставшихся. Итак, магическое число 9/98, что бы это ни значило. И т.д.

Как только мы получим столько записей, сколько захотим, вероятность будущих записей будет равна нулю, поэтому мы никогда не будем переходить. Если мы приближаемся к концу и не подобрали достаточно записей, вероятность будет очень близка к 100%. Например, если нам все еще нужно 8 записей и осталось только 8 записей, вероятность будет 8/8 = 100%, поэтому мы гарантированно возьмем следующую запись.