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