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

Ответ 1

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

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

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

McLeod and Bellhouse, 1983 (1) дают более подробное обсуждение, чем Knuth, а также первое опубликованное доказательство (что я знаю), что алгоритм работает.

Vitter 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 содержит справедливую и репрезентативную выборку элементов, которые алгоритм рассматривал в любое время. Это означает, что вы можете использовать это как онлайн-алгоритм .

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

McLeod and Bellhouse (1983) предоставляют доказательство с использованием математики комбинаций. Это довольно, но было бы немного сложно восстановить его здесь. Поэтому я создал альтернативное доказательство, которое легче объяснить.

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

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

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

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

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

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

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

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

Ссылки

• McLeod, A. Ian и David R. Bellhouse. "Удобный алгоритм для рисования простой случайной выборки". Журнал Королевского статистического общества. Серия C (прикладная статистика) 32.2 (1983): 182-184. (Ссылка)

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

Легко показать, что это дает случайный выбор. После просмотра 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).

Ответ 5

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

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

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

Ответ 6

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

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;

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