Эффективный выбор набора случайных элементов из связанного списка
Скажем, у меня есть связанный список чисел длины N, N очень большой, и я не знаю заранее точное значение N,
Как я могу наиболее эффективно написать функцию, которая будет возвращать k полностью случайные числа из списка?
6 ответов
Для этого есть очень хороший и эффективный алгоритм, использующий метод, называемый отбор проб из пласта.
Позвольте мне начать с истории.
Кнут называет этот алгоритм R на p. 144 его издания 1997 года "Получисленные алгоритмы" (том 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-seen набор результатов содержит элемент либо, если он был частью nрезультат не был заменен --- эта вероятность (s/n)*n/(n+1)=s/(n+1)--- или если элемент был выбран --- с вероятностью s/(n+1),
Определение алгоритма говорит нам, что первый s элементы автоматически включаются в качестве первого n=s члены набора результатов. Следовательно n-seen набор результатов включает в себя каждый элемент с s/n (=1) вероятность, дающая нам необходимый базовый случай для индукции.
Рекомендации
Маклеод, А. Ян и Дэвид Р. Беллхаус. "Удобный алгоритм рисования простой случайной выборки". Журнал Королевского статистического общества. Серия C (Прикладная статистика) 32,2 (1983): 182-184. ( Ссылка)
Виттер, Джеффри С. "Случайная выборка с резервуара". Транзакции ACM по математическому программному обеспечению (TOMS) 11.1 (1985): 37-57. ( Ссылка)
Это называется проблемой отбора проб в резервуаре. Простое решение состоит в том, чтобы назначить случайное число каждому элементу списка, каким вы его видите, а затем сохранить верхние (или нижние) k элементов в порядке, указанном случайным числом.
Я бы предложил: сначала найдите ваши k случайных чисел. Сортировать их. Затем пройдитесь по связанному списку и вашим случайным числам один раз.
Если вы как-то не знаете длину вашего связанного списка (как?), То вы можете получить первые k в массив, затем для узла r сгенерировать случайное число в [0, r), и если оно меньше чем k, заменить r-й элемент массива. (Не совсем уверен, что это не смещение...)
Кроме этого: "Если бы я был тобой, я бы не начал отсюда". Вы уверены, что связанный список подходит для вашей проблемы? Нет ли лучшей структуры данных, например, старого доброго списка плоских массивов.
Если вы не знаете длину списка, вам придется пройти его полностью, чтобы обеспечить случайный выбор. В этом случае я использовал метод, описанный Томом Хотином ( 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;
Я уверен, что вы не имеете в виду что-то простое, так что вы можете уточнить дальше?