Функция, возвращающая случайный элемент из потока неизвестной длины
Добавлено: 18.03.08 в 09:35
Есть некий поток элементов. Вызывая снова и снова функцию getnext(), вы получаете каждый раз следующий элемент из потока, и так до тех пор, пока функция не вернет EOF, что означает, что поток закончился. Гарантировано, что все элементы, полученные таким образом, будут отличаться друг от друга. Вернуться к началу потока, или получать элементы в каком-то другом порядке, кроме как один за другим с помощью getnext(), невозможно.
Известно, что поток когда-нибудь кончается, но заранее про количество элементов ничего не известно.
Требуется: написать функцию, которая, когда ее вызывают (а вызывают ее один раз), возвращает выбранный случайным образом один из элементов потока, притом у каждого из элементов потока одинаковая вероятность быть возвращенным этой функцией.
Функция должна использовать фиксированное количество памяти (иными словами, O(1) памяти).
СПРЯТАТЬ РЕШЕНИЕ/ОТВЕТ
Перебираем весь поток по одному, параллельно храним кандидата (значение, которое мы собираемся вернуть) в переменной $result.
Каждый новый претендент может побить кандидата с вероятностью 1/m, где m - количество претендентов, уже прочитанных из потока.
Схема-код решения (на php):
function getrandom()
{
$m = 0; //thread counter
$result = null; //candidate to return
while ($current = getnext())
{
$m++;
if ( 1/$m >= random() ) //check if pretendent wins candidate
$result = $current;
}
return $result;
}
N.B. random() — несуществующая в php функция, возвращающая случайное действительное число из интервала [0,1]
