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

Question

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

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

Answer 1

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

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

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

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

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

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

Маклеод и Беллхаус (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 -видимый набор результатов содержит элемент, либо если он был частью 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. ( Link )

Answer 2

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

Answer 3

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

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

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

Answer 4

Если вы не знаете длину списка, вам придется пройти его полностью, чтобы обеспечить случайный выбор. В этом случае я использовал метод, описанный Томом Хоутином ( 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).

Answer 5

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

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;

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

Answer 6

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

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

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