Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

алгоритм флойда (программистское)

Скажем, у вас есть файл, в котором тысяча строк, и вам нужно 20 из них выбрать, случайным и равномерным образом. Как вы это сделаете?

Или просто нужно выбрать случайный набор из пяти чисел от 1 до 100, для какой-то цели. Как это сделать?

Эта задача называется "выборка без повторений", и есть несколько известных алгоритмов, которые ее решают в разных ее вариантах. Я вкратце напомню о самых известных из них, а потом расскажу еще об одном, очень простом и красивом, который придумал Флойд.

Задача


Итак, наша цель - выбрать n элементов случайным и равномерным способом из какого-то набора из N элементов. Есть три варианта задачи, от более простого к более сложному:

Оффлайн: Все N элементов даны нам сразу и одновременно (например, в массиве), мы можем делать с ними что угодно.
Онлайн: Мы получаем элементы по одному, и N может быть таким большим, что непрактично их все запоминать (а только выбранные).
Онлайн, размер неизвестен: Мы получаем элементы по одному, нам нужно выбрать из них n, но мы не знаем заранее N - количество элементов. Когда кончатся, тогда кончатся.

Основные алгоритмы для выборки без повторений.


Оффлайн:


1. Самый наивный: выбрать один элемент случайно, потом еще один, и так далее, пока не наберется n. Если выпадет повтор уже выбранного - игнорируем и пробуем еще раз. Этот алгоритм вполне работает, но у него нет строгой гарантии числа шагов, и это многим не нравится. Кроме того, надо быть осторожным и не запускать его, если n очень близко к N - например, если попробовать выбрать так 999 элементов из 1000, последние элементы будет долго искать. Если нужно выбрать больше, чем половину элементов (n > N/2), то следует инвертировать: запустить его для выборки N-n элементов, и считать, что мы выбрали те, что остались.

2. Выберем случайную перестановку всех N элементов, и возьмем первые n в том, что получилось. Если N небольшое, это может быть самым простым и емким с точки зрения исходного кода способом (потому что для генерирования случайной перестановки уже готовая функция часто есть). Если N большое, то это неэффективно, но можно использовать стандартный алгоритм для создания перестановки (выбираем случайный элемент и меняем с первым элементом массива, выбираем случайный из оставшихся и меняем со вторым, итд.), и запустить только первые n шагов. Это дает эффективный алгоритм за O(n), единственный недостаток которого - это что он меняет исходный массив.

Онлайн:


3. Каждую новый элемент, когда мы его видим, выбираем или не выбираем с определенной вероятностью, а именно (n-m)/(N-t), где m - число элементов, которые мы уже выбрали до сих пор, а t - число элементов, которые мы видели до сих пор, не включая этот. Когда мы выберем n элементов, вероятность станет нулевой оттуда и до конца. Можно показать (выкладки не вполне тривиальны), что с этим алгоритмом вероятность любого элемента быть выбранным равна n/N, как и требуется. На первый взгляд это противоречит тому, что мы принимаем решение по его поводу ровно один раз, и используем вероятность (n-m)/(N-t), но только на первый, противоречия нет.
Недостаток этого алгоритма - O(N) операций, т.к. мы делаем выбор для каждого элемента.

Есть алгоритм Виттера, который более хитрым образом решает через много элементов перепрыгнуть и даже не рассматривать, и добивается в итоге усредненного времени выполнения O(n) для онлайн-задачи.

Онлайн, размер неизвестен:


4. Эта задача часто встречается на технических интервью для программистов (иногда для частного случая n=1). Основной алгоритм "выбора с резервуаром" работает так: сначала мы выбираем первые n элементов входного потока, а далее каждый следующий элемент мы подвергаем выбору: если это элемент номер M от начала, то с вероятностью n/M мы выбираем его, и выбрасываем один из ранее выбранных (случайным образом). Простой способ сделать это - сгенерировать случайное число от 1 до M, и если они вышло среди первых 1...n, то именно этот элемент выбосить и заменить на новый.

Такая процедура обеспечивает тот факт, что после шага M для любого M (после n начальных) у каждого элемента был ровно шанс n/M быть выбранным. Действительно, сразу после первых n элементов (M=n) это очевидно, каждый из них выбран с вероятностью 1. Далее, если после шага M-1 каждый в нашем выбранном наборе до сих пор попадал в него с вероятностью n/(M-1), то после M-го шага есть вероятность 1/M, что именно его выбросят ради нового, т.е. с вероятностью (M-1)/M он останется, и умножив это на вероятность дожить до M-1-го шага, получим общую новую вероятность n/(M-1) * (M-1)/M = n/M. Ну а новый элемент будет сохранен тоже с вероятностью n/M просто по определению алгоритма.

Алгоритм Флойда:


5. В 80-х Роберт Флойд придумал простой и элегантный способ решить оффлайн-задачу, не требующий, в отличие от решения с перестановкой, разрушать исходный массив. В алгоритме Флойда для выбора n элементов мы проходим циклом ровно по n элементам массива, и каждый раз в цикле делаем один выбор, так что время работы O(n) без вариантов. Если представить весь массив из N элементов лежащим слева направо, то мы проходим по n самых последних, правых элементов массива. Вот алгоритм Флойда в псевдокоде:

        initialize set S to empty
        for J := N-n + 1 to N do
           T := RandInt(1, J)
           if T is not in S then
             insert T in S
           else
             insert J in S

Предположим, нам надо выбрать 5 элементов из 100. Мы сначала выберем случайный элемент из первых 96, потом из первых 97, из первых 98 и так далее. Но всякий раз, если мы попадем на уже выбранный в прошлом элемент, то выберем не его снова, а как раз тот, который только что добавили (96, 97, 98...).

Мне нравится это представлять, как будто вновь добавленный к начальному отрезку элемент "прикрывает" уже ранее выбранные. Вот подробный разбор того, как мы выбираем 4 числа от 1 до 12. В самом начале мы приготовились запускать цикл, первые 8 элементов у нас рабочий интервал, еще ничего не выбрано:



В первой итерации цикла мы добавляем 9 к рабочему интервалу и выбираем из него один элемент:



Во второй итерации мы добавляем 10 к рабочему интервалу и выбираем из него один элемент, при этом 10 временно прикрывает выбранные ранее элементы:



И так далее:

fl4

Почему эта процедура приводит к равномерному выбору каждого элемента? Интуитивно говоря, те элементы, которые присоединяются к рабочему интервалу позднее, получают компенсацию, когда в своей итерации они "прикрывают" ранее выбранные. Скажем, у каждого из элементов 1-8 было 5 шансов быть выбранными, в каждой из пяти итераций, а у элемента 11 - только два шанса, зато в первый из них у него было три "копии", а не одна.

Чтобы доказать это строго, заметим вначале, что от ничего в алгоритме не зависит от количества итераций: его можно менять как угодно, и получать решение задачи для других параметров. Скажем, в примере выше, до того, как мы запустили цикл, мы "выбрали" 0 элементов из 8, после первой итерации выбрали 1 элемент из 9, потом 2 из 10, 3 из 11 и наконец 4 из 12. Могли продолжать выбирать и дальше, в точности по определению алгоритма. При этом каждая новая итерация увеличивает и n и N, a их разность - размер "начального отрезка", в нашем примере 8 - фиксирован. Если алгоритм работает верно, то при выборе n элементов из N мы должны получить вероятность каждого элемента быть выбранным ровно n/N. Докажем, что это верно индукцией по количеству итераций цикла. В самом начале n=0, N = размер "начального отрезка", в примере выше мы "выбираем" 0 элементов из 8, и у каждого вероятность 0/8 = 0 быть выбранным, все верно. После первой итерации мы выбрали n=1 элемент из N, и у каждого действительно 1/N шансов быть выбранным. Теперь предположим, что это верно после итерации, где мы выбрали n из N. Значит, каждый элемент до сих пор был выбрал с вероятностью n/N, и не выбран с вероятностью (N-n)/N. Теперь мы добавляем новый элемент и выбираем снова, "прикрывая" уже выбранные:

- один из старых элементов либо уже был выбран - и остается таковым с вероятностью 1 - либо не был - и становится таковым с вероятностю 1/(N+1). Новая вероятность того, что он выбран, равна 1 * n/N + 1/(N+1) * (N-n)/N. Приводя к общему знаменателю и сокращая, получаем (n+1)/(N+1).
- только что добавленный элемент выбирается тоже с вероятностью (n+1)/(N+1), потому что в момент выбора мы даем ему n+1 "копий" - его самого, и прикрываем им n выбранных до сих пор элементов.

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

Последнее замечание. Алгоритм Флойда решает "оффлайновую" задачу, и требует знания N заранее, потому что цикл начинается с позиции N-n+1. Но если присмотреться, то можно заметить, что на самом деле его можно считать вариантом алгоритма номер 4 выше - "выбора с резервуаром" n элементов из неизвестного числа. В алгоритме Флойда перед началом работы есть ровно N-n "не выбранных" элементов - весь "начальный отрезок" - и каждая итерация добавляет к ним еще один элемент, и отнимает один, потому что выбирает его. Если мы попробуем посмотреть на алгоритм Флойда "инвертированным" путем, как на способ не выбрать n элементов из N, а "на самом деле" выбрать оставшиеся N-n элементов, то неожиданно выходит, что он:

- "онлайновый": можно продолжать итерацию за итерацией, N-n остается неизменным
- не требует знания N заранее, а только число N-n элементов, которых мы "выбираем" таким образом
- идентичен алгоритму выборки с резервуаром. В терминах алгоритма Флойда выбрать еще один элемент в следующей итерации - это то же, что в выборке с резервуаром "выкинуть" один из элементов - либо существующий, заменяя на новый, либо новый, тем самым не беря его. Все вероятности совпадают (как и следует).
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 26 comments