Алгоритм быстрого случайного выбора

Question

Учитывая массив значений true / false, каков наиболее эффективный алгоритм выбора индекса с случайным значением true.

Простой набросок алгоритма:

a <- the array
c <- 0
for i in a:
    if a[i] is true: c++
e <- random number in (0, c-1)
j <- 0
for i in e:
    while j is false: j++
return j

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

Answer 1

Используйте алгоритм «выбрать случайный элемент из бесконечного списка».

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

Когда вы видите истинное значение, увеличьте счетчик и затем замените ваш выбор текущим индексом с вероятностью P = (1 / счет). (Таким образом, вы всегда выбираете первое, что найдете ... затем вы можете переключиться на второе с вероятностью 1/2, затем вы могли бы переключиться третьему с вероятностью 1/3 и т. д.)

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

См. этот ответ для примера реализации LINQ простого алгоритма "выбрать случайный элемент"; для этого потребуются незначительные изменения.

Answer 2

Создайте список с индексами, которые указывают на значения true, и выберите один из них случайным образом. Требуется O (n) для обхода списка и одна попытка для случайного числа.