Как выбрать 100 случайных элементов из бесконечного потока, не сохраняя его целиком?
Как выбрать 100 случайных элементов из бесконечного потока, не сохраняя его целиком? Кандидаты идут без конца, а память ограничена. Решение — метод Reservoir sampling. Первые сто элементов сразу попадают в резервуар, а каждый следующий добавляется с вероятностью 100/i, вытесняя случайного из выборки. Так у вас всегда будет ровно сто элементов, и у каждого кандидата шанс оказаться в выборке равен.
7 947 просмотров
Канал в каталоге MAXimeter
13 050 подписчиков · IT и технологии