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

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

Эскиз простой алгоритм

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

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

источник

2009-12-03 momeara

Любопытно узнать, в каких приложениях используются эти типы алгоритмов? Когда-то мне приходилось сталкиваться с подобным вопросом, учитывая массив бесконечного размера, первые русские места заполняются 1, остальные - нули. Теперь этот массив передается новому пользователю (который не знает значения n). Теперь найдите алгоритм, чтобы отметить место, где находится последний 1. Это я решил путем двоичного поиска. Приведите несколько примеров, где они используются. – avd

Около двух экземпляров: http://stackoverflow.com/questions/1133942/what-is-the-most-efficient-way-to-pick-a-random-card-from-a-deck-when-some-cards. В этом вопросе массив имеет размер 52, хотя это может повлиять на ответы (например, вы уверены, что arary размера 52 подходит для памяти, тогда как 'a' здесь может не подойти). –

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

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

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

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

См. this answer для примера реализации LINQ простого алгоритма «выбрать случайный элемент»; он просто нуждается в небольших настройках.

источник

2009-12-03 15:32:06

Еще несколько деталей и доказательство здесь: http://stackoverflow.com/questions/1133942/what-is-the-most-efficient-way-to-pick-a-random-card-from-a-deck- когда-некоторые-карты/1134286 # 1134286. Этот вопрос является функционально дубликатом этого, хотя и сформулированным немного по-другому. Мой инстинкт заключается в том, что он, скорее всего, будет медленнее, чем двухпроходный алгоритм, предполагая данные в памяти. Но стоит проверить, если двухпроходная производительность неприемлема по любой причине. –

@Steve: Это зависит от разреженности «истинных» значений и стоимости генерации случайного числа. Если у вас миллион записей в списке, только 2 из которых являются «истинными», то это, вероятно, будет победой. Если, с другой стороны, у вас есть миллион записей * все * из которых являются истинными, алгоритм с двумя проходами, вероятно, будет быстрее. В общем, я просто люблю элегантность однопользовательских постоянных алгоритмов хранения :) –

Хех, я просто сделал тот же комментарий о разреженности в ответе Йоханнеса. Я тоже согласен с элегантностью, хотя я немного волнуюсь, что использование большого количества случайных чисел затрудняет анализ последствий любых слабых мест в RNG. –

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

источник

2009-12-03 15:27:31 Joey

Это, безусловно, быстрее, чем то, что я придумал, хотя он использует рабочее пространство O (n), где мое использует только постоянное рабочее пространство. Таким образом, все еще может быть место для улучшения. – momeara

Это, конечно, быстрее? Если истинные значения очень редки, то это почти наверняка быстрее. Если ложные значения очень редки, то это почти наверняка медленнее. Где точка безубыточности, я не знаю. –

Да, конечно, распределение значений true/false имеет значение для вопроса, какой алгоритм более эффективен. Но когда это не известно, все ставки уходят, как обычно. Тем не менее, я считаю, что ответ Джона очень хороший и, вероятно, будет лучше этого. – Joey

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

ответ

Смежные вопросы