Резервуарная выборка: равномерная выборка из потока неизвестной длины

Цель

За один проход равномерно случайно выбрать k элементов последовательности, длина которой неизвестна до завершения, используя память независимо от её длины. Примеры — выбор строк журнала для проверки, строк большого экспорта или примеров для отчёта без загрузки всего объёма.

Предварительные условия

Генератор псевдослучайных чисел с функцией равномерного выбора целого. Модуль Python random, согласно документации основанный на вихре Мерсенна, подходит для статистической выборки. Та же документация предупреждает, что он не предназначен для безопасности: используйте secrets, если противник не должен предсказывать выборку. Поток читается один раз, k элементов помещаются в память.

Шаги

1. Сохраните первые k элементов в списке — резервуаре.
2. Для каждого следующего элемента с номером i, считая с 1, равномерно выберите целое j от 1 до i. Если j не больше k, перезапишите ячейку резервуара j этим элементом; иначе отбросьте элемент.
3. После завершения потока резервуар и есть выборка. Порядок его ячеек ничего не означает; перемешайте её, если порядок важен при дальнейшей обработке.
4. Убедитесь в равномерности. Элемент i входит с вероятностью k/i. Элемент резервуара переживает приход элемента t с вероятностью 1 - 1/t = (t-1)/t. Произведение вероятностей сохранения для t от i+1 до n сокращается до i/n, поэтому (k/i) * (i/n) = k/n — одинаково для каждого элемента. Это относится и к первым k: они входят с вероятностью 1 и сохраняются с вероятностью k/n.
5. Частный случай k = 1: заменяйте единственную ячейку с вероятностью 1/i.
6. Проверьте на небольшом потоке, например из 10 элементов при k = 3: многократно повторяйте процедуру и проверяйте, что частота включения каждого элемента приближается к 0.3. Проверьте также, что код никогда не запрашивает длину.
7. Задавайте начальное значение генератора в тестах для воспроизводимости и записывайте его в журнал в рабочей среде, чтобы выборку из отчёта можно было воспроизвести.

Ожидаемый результат

Каждый элемент находится в выборке с вероятностью ровно k/n; один случайный выбор на элемент, память пропорциональна k, длина потока никогда не нужна.

Ограничения и основания метода

Выборка равномерна по элементам, а не по времени или байтам; поток со всплесками выбирается по числу элементов. Резервуары нескольких параллельных потоков нужно объединять с весами, пропорциональными числу их элементов. Существуют взвешенные варианты и варианты с перескоками вперёд для сокращения числа случайных выборов; здесь они не рассматриваются. Корректность следует из арифметики шага 4; измерения не заявляются.