August 22nd, 2013

moose, transparent

два срока



Это Линди Ингланд. Она издевалась над заключенными в тюрьме Абу-Грейб в Ираке, пытала их, заставляла себя унижать, фотографировалась рядом. Военный трибунал присудил ее к 3 годам тюрьмы.



Это Брэдли Мэннинг. Он передал Викиликс большое количество секретных армейских и дипломатических материалов, которые были обнародованы. В результате этого обнародования ни один человек, насколько известно, не поплатился жизнью или свободой, не возникло никакой новой угрозы действиям американской армии; Госдепартамент пришел к выводу, что рассекречивание дипломатических телеграмм привело к определенному конфузу, но не нанесло значительного ущерба внешней политике США.

Военный трибунал присудил его сегодня к 35 годам тюрьмы.
moose, transparent

цветное

Двадцать раскрашенных знаменитых черно-белых фотографий.

К моему удивлению, многие из них мне понравились (увидев название, я решил, что это обязательно будет безвкусно и аляповато. Не знаю, почему так решил)

Подросток в трущобах Балтимора, 1938:

moose, transparent

не ориентируюсь в современной жизни

Гм, кажется, вот этот милый комикс сломал мой орган эмпатии. Ну или по крайней мере его парализовал на время.

Для тех, кто не читает по-английски, не смотрит на картинки, или просто лень, вот его пересказ:

- автор - гей, да не простой, а "золотой" - ни разу не занимался сексом с женщиной и гордится этим;
- вместе с тем, в последние годы он обнаружил, что его особенно тянет на транс-мужчин, т.е. физиологически женщин от рождения, которые считают себя на самом деле мужчинами и стремятся сменить пол;
- более того, его обычно привлекают не просто такие трансгендерные мужчины, а те из них, кто тестостерон уже принимает, а операцию еще (или вообще) не сделал, и поэтому у них там, внизу - ну ясно что;
- и все бы ничего, но некоторые его друзья, неотесанные болваны, выражают недоумение тем, как это он спит с людьми, у которых женские приватные части, но продолжает считать себя 100%-ным геем;
- и вот он нарисовал этот комикс, чтобы объяснить им и вообще всем, как они ничего не понимают, и что он 100%-ный гей и никакой не стрейт всего лишь потому, что занимается стрейт-сексом со своим транс-бойфрендом с женской анатомией.

Мой орган эмпатии сломался и отказывается ощущать сочувствие по поводу этой гигантской проблемы.

Отдельно отмечу прекрасную фразу из комментариев там: "I am a trans man and I love my vagina".
moose, transparent

дневные стихи: максимов

ПОЭТ-ПИСЕЦ

        Пока не требует поэта
        К священной жертве Аполлон...
                Пушкин

Он долго ждет, безмолвствуя, как тот
Египетский писец, от века безутешный,
Пока птицеголовый Тот
Найдет его во тьме кромешной.

И доску даст с папирусом, и он
Поведает, познав сияние и тленье,
Птицеголовым окрылен,
Свои глухие сновиденья.


Д.Е.Максимов (литературовед, поэт, 1904-1987)
moose, transparent

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

Скажем, у вас есть файл, в котором тысяча строк, и вам нужно 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 элементов, которых мы "выбираем" таким образом
- идентичен алгоритму выборки с резервуаром. В терминах алгоритма Флойда выбрать еще один элемент в следующей итерации - это то же, что в выборке с резервуаром "выкинуть" один из элементов - либо существующий, заменяя на новый, либо новый, тем самым не беря его. Все вероятности совпадают (как и следует).
moose, transparent

stricken mass distributions (англ.)

Еще одна история из воспоминаний математика Ральфа Боаса (предыдущая см. тут). Эту я не берусь перевести на русский (если кто-то хочет попробовать - пожалуйста), поэтому просто процитирую в оригинале. MR означает "Mathematical Reviews", математический журнал, который публикует краткие обзоры статей в других журналах.

MR sent me a paper by a Japanese author who kept referring to “stricken mass distributions”. I couldn’t figure out what those were, and finally wrote to the editor of the journal in which the paper had appeared. He sent me a copy of the referee’s report, which had been sent to the author; this said, in part, “The term ‘generalized mass distribition’ is no longer used. The word ‘generalized’ should be stricken.”