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

Val Petruchek

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

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

« Почему WordPress — гавно. Часть третья
Киев — не Москва »

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

12.03.07 @ 07:00 — Problems, Programming

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

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

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

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

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

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

Решение:
Заполняем возвращаемый массив первыми n элементами. Затем перебираем поток до конца, i-ый элемент попадает в возвращаемый массив с вероятностью n/i. Если i-ый элемент попадает в массив, то он выбивает один из его элементов случайным образом с одинаковой для каждого элемента вероятностью 1/n.

Схема-код решения (на php):

function getrandomarray($n)
{
$i 0//thread counter
$result = array(); //to return
while ($current getnext())
    {
    
$i++;
    if (
$i <= $n//first $n candidates take their places
        
$result[$i-1] = $current;
    else{
        if (
$n/$i random()) //checking if new candidate won a place
            
$result[rand() % $n] = $current//choosing random place for winner
        
}
    }
return 
$result;
}

N.B. random() — несуществующая в php функция, возвращающая случайное действительное число из интервала [0,1]

No Comments »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a comment

  
Реклама::

 
Реклама::