Усложняем задачу о выборе случайного элемента из потока неизвестной длины:
Есть некий поток элементов. Вызывая снова и снова функцию 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]
