Эта статья не является подробным объяснением и доказательством этого алгоритма, а скорее описывает интуицию, лежащую в основе этого алгоритма, и основы того, как он работает.
Проблема: учитывая список из 1 миллиона имен, выберите из него 100 случайных имен, чтобы каждое число было выбрано с равной вероятностью.
Легко, я могу использовать «честный» генератор случайных чисел, который генерирует 100 индексов от 0 до 1 миллиона. Затем я могу выбрать соответствующие имена из списка.
подождите! вы не будете знать заранее, сколько имен в списке.
Хм, я могу просмотреть весь список и найти количество списков (1 миллион).
Теперь я могу использовать ту же технику, что и раньше, с помощью генератора случайных чисел.
ой, я не упоминал раньше! вы не можете получить доступ к именам напрямую по индексу, вы увидите список имен по очереди.
Ну, я могу дважды просмотреть список. На первом проходе я могу узнать, сколько имен находится в списке. (1 миллион)
Затем я воспользуюсь генератором случайных чисел, чтобы выбрать 100 индексов.
Затем я снова пройдусь по списку, чтобы выбрать соответствующее имя.
Извините, что сломал вам это! вместо фиксированного списка имен это будет поток бесконечных имен, которые мы не хотим хранить. И нам нужно знать в режиме реального времени, что на данный момент выбрано 100 номеров.
Вот где решение проблемы - отбор проб из коллектора.
Как это работает?
Сначала мы заполняем наш массив из 100 имен первыми 100 именами, которые мы видим в потоке.
Когда приходит 101-е имя, какова вероятность того, что каждое 101 имя будет в нашем массиве из 100 имен? Просто, 100/101.
Поэтому, когда мы решаем выбрать 101-е имя и выбросить имя из существующего массива, нам нужно поддерживать это соотношение 100/101.
Таким образом, мы сохраняем вероятность выбора 101-го элемента как 100/101. Мы можем сгенерировать случайное число от 0 до 1, и если оно ниже (100/101), мы выберем 101-й элемент и выберем любой случайный элемент из нашего массива 100 имен.
Вероятность выпадения любого числа: (1/100) * (100/101) = 1/101.
Следовательно, вероятность того, что любое число останется, равна 1– (1/101) = 100/101.
Итак, мы выбрали новый элемент с вероятностью 100/101, и для каждого существующего элемента вероятность остаться равна 100/101.
Это можно обобщить для 102,103… N, где вероятность остается той же 100 / N. Например, мы выбрали 100 чисел с равной вероятностью из бесконечного потока данных в определенный момент времени.
Ссылки:
