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

StackOverflow https://stackoverflow.com/questions/54059

Вопрос

Скажем, у меня есть связанный список чисел длины N. N очень велик, и я заранее не знаю точного значения N.

Как наиболее эффективно написать функцию, которая будет возвращать k полностью случайные числа из списка?

Это было полезно?

Решение

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

Позвольте мне начать с того, что я дам вам его история:

Кнут называет этот алгоритм R на стр.144 его издания «Получисловые алгоритмы» 1997 года (том 2 «Искусства компьютерного программирования») и содержит там некоторый код.Кнут приписывает алгоритм Алану Г.Уотерман.Несмотря на долгие поиски, мне не удалось найти оригинальный документ Уотермана, если он существует, и, возможно, именно поэтому вы чаще всего будете видеть Кнута, цитируемого как источник этого алгоритма.

Маклеод и Беллхаус, 1983 год. (1) предоставить более подробное обсуждение, чем у Кнута, а также первое опубликованное доказательство (которое мне известно) того, что алгоритм работает.

Виттер 1985 г. (2) рассматривается алгоритм R, а затем представлены еще три алгоритма, которые обеспечивают тот же результат, но с некоторыми изменениями.Вместо того, чтобы делать выбор, включать или пропускать каждый входящий элемент, его алгоритм заранее определяет количество входящих элементов, которые нужно пропустить.В его тестах (которые, по общему признанию, уже устарели) это значительно сократило время выполнения за счет отказа от генерации случайных чисел и сравнения каждого входящего числа.

В псевдокод алгоритм такой:

Let R be the result array of size s
Let I be an input queue

> Fill the reservoir array
for j in the range [1,s]:
  R[j]=I.pop()

elements_seen=s
while I is not empty:
  elements_seen+=1
  j=random(1,elements_seen)       > This is inclusive
  if j<=s:
    R[j]=I.pop()
  else:
    I.pop()

Обратите внимание, что я специально написал код, чтобы не указывать размер входных данных.Это одно из замечательных свойств этого алгоритма:вы можете запустить его, не зная заранее размер входных данных, и это все еще гарантирует, что каждый элемент, с которым вы сталкиваетесь, имеет равную вероятность оказаться в R (то есть предвзятости нет).Более того, R содержит справедливую и репрезентативную выборку элементов, которые алгоритм всегда учитывал.Это означает, что вы можете использовать это как онлайн-алгоритм.

Почему это работает?

Маклеод и Беллхаус (1983) приводят доказательство, используя математику комбинаций.Оно красивое, но восстановить его здесь будет немного сложно.Поэтому я предложил альтернативное доказательство, которое легче объяснить.

Продолжим доказательство по индукции.

Скажем, мы хотим сгенерировать набор s элементы и что мы уже видели n>s элементы.

Предположим, что наш текущий s элементы уже выбраны с вероятностью s/n.

По определению алгоритма выбираем элемент n+1 с вероятностью s/(n+1).

Каждый элемент, уже являющийся частью нашего набора результатов, имеет вероятность 1/s быть замененным.

Вероятность того, что элемент из n-виденный набор результатов заменяется в n+1-видимый набор результатов поэтому (1/s)*s/(n+1)=1/(n+1).И наоборот, вероятность того, что элемент не будет заменен, равна 1-1/(n+1)=n/(n+1).

Таким образом n+1-seen результирующий набор содержит элемент, если он был частью n-виден набор результатов и не был заменен --- эта вероятность равна (s/n)*n/(n+1)=s/(n+1)---или если элемент был выбран---с вероятностью s/(n+1).

Определение алгоритма говорит нам, что первый s элементы автоматически включаются в качестве первых n=s члены результирующего набора.Следовательно n-seen результирующий набор включает в себя каждый элемент с s/n (=1) вероятность, дающая нам необходимый базовый случай для индукции.

Рекомендации

  1. Маклеод, А.Ян и Дэвид Р.Колокольня.«Удобный алгоритм для рисования простой случайной выборки». Журнал Королевского статистического общества.Серия C (Прикладная статистика) 32.2 (1983 г.):182-184.(Связь)

  2. Виттер, Джеффри С.«Случайная выборка с резервуаром». Транзакции ACM по математическому программному обеспечению (TOMS) 11.1 (1985):37-57.(Связь)

Другие советы

Это называется Отбор проб из резервуара проблема.Простое решение — присвоить случайное число каждому элементу списка в том виде, в каком вы его видите, а затем сохранить k верхних (или нижних) элементов в порядке, упорядоченном по случайному числу.

Я бы предложил:Сначала найдите k случайных чисел.Отсортируйте их.Затем один раз просмотрите как связанный список, так и случайные числа.

Если вы каким-то образом не знаете длину вашего связанного списка (как?), то вы можете захватить первый k в массив, затем для узла r сгенерировать случайное число в [0, r), и если оно меньше чем k, замените r-й элемент массива.(Не совсем уверен, что это не предвзятость...)

Кроме этого:«Если бы я был тобой, я бы не начинал отсюда». Вы уверены, что Linked List подходит для вашей проблемы?Нет ли лучшей структуры данных, такой как старый добрый список плоских массивов?

Если вы не знаете длину списка, вам придется пройти его полностью, чтобы обеспечить случайный выбор.В этом случае я использовал метод, описанный Томом Хотином (54070).Просматривая список, вы сохраняете k элементы, которые формируют ваш случайный выбор к этому моменту.(Изначально вы просто добавляете первый k элементы, с которыми вы столкнетесь.) Тогда с вероятностью k/i, вы заменяете случайный элемент из вашего выбора на i-й элемент списка (т.е.элемент, в котором вы находитесь в данный момент).

Легко показать, что это дает случайный выбор.После просмотра m элементы (m > k), у нас есть то, что каждый из первых m элементы списка являются частью вашего случайного выбора с вероятностью k/m.То, что это изначально справедливо, тривиально.Тогда для каждого элемента m+1, вы помещаете его в свой выбор (заменяя случайный элемент) с вероятностью k/(m+1).Теперь вам нужно показать, что все остальные элементы также имеют вероятность. k/(m+1) быть избранным.Мы имеем, что вероятность равна k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (т.е.вероятность того, что элемент был в списке, умноженная на вероятность того, что он все еще там).С помощью исчисления вы можете прямо показать, что это равно k/(m+1).

Что ж, вам нужно знать, что такое N, по крайней мере, во время выполнения, даже если это потребует дополнительного прохода по списку для их подсчета.Самый простой алгоритм сделать это — просто выбрать случайное число из N и удалить этот элемент, повторив k раз.Или, если разрешено возвращать повторяющиеся номера, не удаляйте элемент.

Если у вас нет ОЧЕНЬ большого N и очень строгих требований к производительности, этот алгоритм работает с O(N*k) сложность, которая должна быть приемлемой.

Редактировать:Неважно, метод Тома Хотина намного лучше.Сначала выберите случайные числа, затем пройдите по списку один раз.Я думаю, та же теоретическая сложность, но ожидаемое время выполнения гораздо лучше.

Почему ты не можешь просто сделать что-то вроде

List GetKRandomFromList(List input, int k)
  List ret = new List();
  for(i=0;i<k;i++)
    ret.Add(input[Math.Rand(0,input.Length)]);
  return ret;

Я уверен, что вы не имеете в виду что-то такое простое, поэтому не могли бы вы уточнить?

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top