?

Log in

алгоритм флойда (программистское) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

алгоритм флойда (программистское) [авг. 22, 2013|05:56 pm]
Anatoly Vorobey
Скажем, у вас есть файл, в котором тысяча строк, и вам нужно 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 элементов, которых мы "выбираем" таким образом
- идентичен алгоритму выборки с резервуаром. В терминах алгоритма Флойда выбрать еще один элемент в следующей итерации - это то же, что в выборке с резервуаром "выкинуть" один из элементов - либо существующий, заменяя на новый, либо новый, тем самым не беря его. Все вероятности совпадают (как и следует).
СсылкаОтветить

Comments:
[User Picture]From: kray_zemli
2013-08-22 03:11 pm
Утверждается, что ваш любимый алгоритм O(n). Однако при этом используется структура set, работа с которой, если я не ошибаюсь, в общем случае O(log n), соответственно сложность O(n*log n). Не?
(Ответить) (Thread)
[User Picture]From: avva
2013-08-22 03:24 pm
Нет, можно использовать множество, основанное на хэш-таблице, у которого время доступа в среднем O(1) - т.е. если совсем строго, то в худшем случае O(log n), но на практике в этом случае используют усредненное время и относятся как к O(1).
(Ответить) (Parent) (Thread)
[User Picture]From: kray_zemli
2013-08-22 03:33 pm
В хеш-таблицах log n есть, просто он замаскирован в константе. А то так можно сказать, что и Radix Sort сортирует за O(N). И зачем тогда, спрашивается, люди с алгоритмами сортировки O(NlogN) заморачиваются?

PS: Как говорят физики, логарифм -- не функция.
(Ответить) (Parent) (Thread)
[User Picture]From: kray_zemli
2013-08-22 03:52 pm
Хотя нет -- да, на практике у хэша константа. Логарифм там, получается, запрятан в разрядности хэш-функции, которой обычно не заморачиваются, потому для практически интереса не представляет.

Зато второй недостаток -- необходимость иметь память под эту вашу хеш-таблицу -- на практике уже может иметь значение. Для остальных ведь алгоритмов она не требуется, если N известно.
(Ответить) (Parent) (Thread)
From: a_shen
2013-08-22 03:37 pm

два технических замечания:

1) не очень понятно, в чём разница между off-line и on-line и в чём проблема сохранения массива: можно применить off-line алгоритм, чтобы выбрать номера элементов из 1..N, и потом уже прочесть соответствующие элементы.

2) недостаточно проверить, что вероятность каждого элемента быть выбранным правильна, они ещё должны быть зависимы правильным образом.
(Ответить) (Thread)
[User Picture]From: avva
2013-08-22 04:08 pm

Re: два технических замечания:

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

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

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

2) Вы правы, конечно - я опустил это для простоты изложения, но вообще говоря, все описанные алгоритмы действительно генерируют равномерную случайную выборку, но это надо отдельно строго доказывать.
(Ответить) (Parent) (Thread)
[User Picture]From: kray_zemli
2013-08-22 04:25 pm

Re: два технических замечания:

Хранить номера элементов не обязательно так же накладно, как сами элементы. И, кстати, оффлайн алгоритмы 1-2 имеют ещё одно отличие: они меняют порядок следования элементов. Это может быть важно, если мы хотим его скрыть.
(Ответить) (Parent) (Thread)
From: a_shen
2013-08-22 05:43 pm

Re: два технических замечания:

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

Про 2) - скорее я хотел сказать, что если с самого начала стараться спрашивать, какова условная вероятность выбора второго элемента, если первый выбран или не выбран, то необходимые параметры для случайных битов появляются сами собой...
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-08-22 06:00 pm

Re: два технических замечания:

Почему странная? Как раз логичная, представьте, например, что N - размер файла, очень большого, что не укладывается в память. Свой вывод, можно представить, алгоритм тоже пишет "куда-то", например в файл, и не считать его частью его рабочей памяти.
(Ответить) (Parent) (Thread)
From: a_shen
2013-08-22 06:10 pm

Re: два технических замечания:

Так понятно - я просто удивлялся, когда речь шла об оценке O(n) для памяти
(Ответить) (Parent) (Thread)
[User Picture]From: winpooh
2013-08-22 04:13 pm
Интересно, во сколько раз больше комментариев соберёт эта запись относительно пред-предыдущей (про комикс)?
(Ответить) (Thread)
[User Picture]From: kray_zemli
2013-08-22 04:27 pm
Ну, если та самая запись пиарила ЛГБТ-болото, то эта запись пиарит другое болото: ResearchGate.
(Ответить) (Parent) (Thread)
[User Picture]From: janatem
2013-08-22 05:28 pm
В условии говорится, что надо выбирать «случайным и равномерным образом», но в предлагаемых решениях используется более слабая формулировка, что элементы должны быть выбраны с равной вероятностью.

Плахов предлагал более общую задачу варианта «онлайн, размер неизвестен» (в ослабленной в вышеуказанном смысле формулировке), где вместо равенства вероятностей требуется их пропорциональность заданным весам. Мое решение в вырожденном случае равных весов совпадает с алгоритмом (4).
(Ответить) (Thread)
[User Picture]From: alaev
2013-08-23 03:29 pm
- в предлагаемых решениях используется более слабая формулировка

А в чём разница?
(Ответить) (Parent) (Thread)
[User Picture]From: janatem
2013-08-23 03:57 pm
В том, что равномерность (сильное условие) подразумевает, что все комбинации — n-элементные подмножества — могут быть выбраны равновероятно, а в решениях показано лишь, что все элемены выбираются с равной вероятностью. Очевидно, что из первого следует второе, но в обратное неверно. Например, для n=2 и четного N можно разбить всё множество на пары фиксированным образом, а потом случайным образом выбрать пару. Тогда слабое условие будет выполнено, а сильное — нет.

(Кстати, я невнимательно читал комментарии, такое замечание было выше (пункт 2)).
(Ответить) (Parent) (Thread)
[User Picture]From: alaev
2013-08-23 05:53 pm
Да, это мы уже обсудили.
(Ответить) (Parent) (Thread)
[User Picture]From: kray_zemli
2013-08-22 05:58 pm
А нафига это надо? Это использует гугль? И зачем?
(Ответить) (Thread)
[User Picture]From: pilpilon
2013-08-22 07:10 pm
это отличная запись ( особенно если кто решил переписать скриптик заливки на аудиоплеер)
(Ответить) (Thread)
[User Picture]From: migmit
2013-08-22 09:37 pm
> выкладки не вполне тривиальны

Эм... разве там нужны выкладки?
(Ответить) (Thread)
From: captain_tylor
2013-08-22 10:20 pm
У меня как раз сейчас похожая задача - выбрать n из N, но вероятность взвешенная.
(Ответить) (Thread)
From: 173175973
2013-08-23 11:16 am
(Ответить) (Thread)
[User Picture]From: alaev
2013-08-23 03:37 pm
По поводу алгоритма 3: в теории вероятностей есть забавная разница между событием, которое обязательно происходит, и событием, которое происходит с вероятностью 1. Алгоритм обязательно должен выбрать n чисел, а если использовать те формулы, то он выберет их только лишь с вероятностью 1 (а с вероятностью 0 выберет меньшее число).

В реализации реального алгоритма с какой-нибудь функцией random() разницы, конечно, не будет. :)
(Ответить) (Thread)
[User Picture]From: janatem
2013-08-23 04:08 pm
В дискретном случае (когда пространство элементарных событий конечно) этой разницы нет. Правда, говоря об алгоритмах, мы выходим за рамки теорвера, и нужно сделать оговорку для случая, когда алгоритм не останавливается. Полагаю, что в этом случае вероятность события не определена, и вряд ли можно придумать разумное доопределение.
(Ответить) (Parent) (Thread)
[User Picture]From: alaev
2013-08-23 05:52 pm
При фиксированных N и n пространство конечно, и Вы, пожалуй, правы на 98%.

Но коль скоро в задаче есть параметры, мы имеем дело не с одной случайной величиной, а с последовательностью, пронумерованной через N и n. Тут некоторый зазор для казуистики остаётся. :)

Например, пусть у нас есть последовательность независимых случайных величин xn, которые выдают 1 с вероятностью 1 и выдают 0 с вероятностью 0. Тогда вероятность того, что все они равны 1, тоже равна 1. Но это вовсе не значит, что событие, когда одна из них выдаст 0, невозможно.
(Ответить) (Parent) (Thread)
[User Picture]From: stdray
2013-08-24 12:17 pm
Я правильно понимаю, что в случае n = N, мы выберем в точности исходную последовательность?

>заметим вначале, что от ничего в алгоритме не зависит от количества итераций
Видимо, один предлог лишний.
(Ответить) (Thread)
[User Picture]From: freedom_of_sea
2013-08-26 09:40 am

ещё наивнее

я вызываю sort передавая ему функцию возвращающую случайно 0 или 1
(Ответить) (Thread)