Как выбрать 100 случайных из бесконечного потока и не хранить его целиком


Кандидаты идут потоком, конца не видно, а память ограничена. Reservoir sampling решает это за один проход: первые сто попадают в резервуар сразу, а каждый следующий i-й заходит с вероятностью 100/i и вытесняет случайного из выборки. В итоге держишь в памяти ровно сто элементов, но у каждого кандидата шанс попасть в выборку одинаковый.