Функция, возвращающая случайный элемент из потока неизвестной длины

Val Petruchek

подписывайтесь, а то хуже будет!  

ПОДПИСЫВАЙТЕСЬ НА RSS

« Борьба с хронофагами
Раскрасить текст программы »

Функция, возвращающая случайный элемент из потока неизвестной длины

24.02.07 @ 02:37 — Problems, Programming

Есть некий поток элементов. Вызывая снова и снова функцию getnext(), вы получаете каждый раз следующий элемент из потока, и так до тех пор, пока функция не вернет EOF, что означает, что поток закончился. Гарантировано, что все элементы, полученные таким образом, будут отличаться друг от друга. Вернуться к началу потока, или получать элементы в каком-то другом порядке, кроме как один за другим с помощью getnext(), невозможно.

Известно, что поток когда-нибудь кончается, но заранее про количество элементов ничего не известно.

Требуется: написать функцию, которая, когда ее вызывают (а вызывают ее один раз), возвращает выбранный случайным образом один из элементов потока, притом у каждого из элементов потока одинаковая вероятность быть возвращенным этой функцией.

Функция должна использовать фиксированное количество памяти (иными словами, O(1) памяти).

(via avva)

Решение:
Перебираем весь поток по одному, параллельно храним кандидата (значение, которое мы собираемся вернуть) в переменной $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]

1 Comment »

  1. […] Усложняем задачу о выборе случайного элемента из потока неизвестной длины: […]

    Pingback by Функция, возвращающая N случайных элементов из потока неизвестной длины — 12.03.2007 @ 07:00

RSS feed for comments on this post. TrackBack URI

Leave a comment

  
Реклама::

 
Реклама::