Учитывая список неизвестной длины, вернуть случайный элемент в нем, отсканировав его только 1 раз

Question

Учитывая список неизвестной длины, вернуть случайный элемент в нем, отсканировав его только 1 раз.

Моя идея:

Аналогичным алгоритмом является выборка из резервуара (опубликовано другими). Но это слишком сложно, потому что нужно запускать rand () и сохранять k узлов каждую итерацию.

Есть ли лучшее решение? O (n) время и O (1) пространство?

Answer 1

Почему вы против отбора проб из пласта? Вы делаете это с k = 1. Существуют небольшие оптимизации (например, вам не нужно выбирать 1 из k, так как k = 1), но это правильный подход. Вы можете попытаться оптимизировать, продолжая обрабатывать фиксированное окно за раз, выполнить математические расчеты с равной вероятностью, если вам нужно выбрать какой-либо элемент в вашем окне вместо того, который у вас есть, и т. Д., Чтобы минимизировать вызовы rand () по более дорогостоящему более сложному алгоритму, но вы все равно будете в конечном итоге отбирать пробы из пласта.

Answer 2

Вы используете отбор проб из резервуара .

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

Это прекрасно работает, если вы хотите, чтобы размер случайной выборки равнялся 1, и если все элементы имеют одинаковый вес.

Когда вы упростили код с k, равным 1, и без явного взвешивания, это все еще выборка из резервуара.

Не все генераторы псевдослучайных чисел работают с одинаковой скоростью; выберите быстрый.

---

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

Ссылка на Википедию показывает эквивалентность перемешиванию Йейтса-Фишера / Кнута. Если бы вы спросили, что будет означать одно и то же случайное число на каждом шаге шаффла, вы будете лаять.

Answer 3

См. кулинарную книгу по Perl для алгоритма , которую вы легко адаптируете к C ++.

По сути, сканируйте список один раз, и для каждой записи с индексом, который вы прочитали, сохранитеэто если случайное число от 0 до i + 1 меньше 1.

Результатом является последняя сохраненная запись.

Answer 4

Раствор в С (осуществление отбора проб из резервуара с k = 1): Вы можете использовать «unsigned long long» для подсчета.

unsigned int chosen, num, count;
count = 1;
get_number(&chosen);
while (get_number(&num)) {
    count++;
    if (rand() % n == 0) chosen = num; 
}

Сохранять k узлов за одну итерацию легко, когда k = 1.
Он запускает rand () каждый раз, что довольно тяжело. Вы можете получить разумные результаты с гораздо более простой псевдослучайной функцией. Но это сделает код более сложным, а не более простым.