Category: мода

Category was added automatically. Read all entries about "мода".

moose, transparent

всячина

  1. Прошлой ночью был ужасный ливень, такие сильные редко бывают в Израиле - но длился всего 10 минут, и все, как выключили. Разверзлись хляби небесные - и тут же сверзлись обратно.

  2. Подумалось вдруг, что в Израиль с опозданием пришла хипстерская мода - вижу вокруг себя огромное количество бородатых молодых людей, с серьезными такими бородами. Вроде бы еще пять лет назад их было намного меньше. Может, это именно в Тель-Авиве так?

  3. Понравилось предложение из статьи двоих физиков (на всякий случай проясню, что я в этом предложении ничего не понимаю):

    "Can anyone seriously claim that the finiteness of the perturbative S-matrix elements of a badly divergent perturbation series settles the question of whether the soft graviton state produced in this process is a normalizable state in Fock space?"

    Риторика хорошая просто. Can anyone seriously claim? [via Peter Woit]

  4. Нейт Сильвер про Ниссима Талеба: "It's a bit ironic that you used to have interesting things to say and now that you no longer have skin in the game you're just a garden-variety troll." В целом согласен.

  5. На работе у принтера лежит пачка бумаги под названием "Stress-free paper".



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

  6. Это тоже обнаружено у принтера. Чем больше всматриваюсь в это, тем непонятнее (можно нажать для увеличения).

    paper.jpg
moose, transparent

как стать несчастным

14 привычек очень несчастных людей (англ.)

Меня редко привлекают книги и советы по самоусовершенствованию, но неожиданно понравился этот набор советов, как стать несчастным. Несмотря на то, что "уловка" там совершенно прозрачная, почему-то это все равно хорошо работает и убеждает, по крайней мере так мне показалось. Переведу только названия каждого пункта (в оригинале подробно объясняется, как это правильно делать, чтобы стать максимально несчастным).

1. Бойтесь, очень бойтесь денежных потерь.
2. Изнывайте от скуки.
3. Постройте собственный имидж на своих проблемах.
4. Ссорьтесь.
5. Приписывайте плохие намерения.
6. Делайте все только для личной пользы.
7. Никогда не благодарите.
8. Будьте всегда наготове, культивируйте тревожность.
9. Вините ваших родителей.
10. Не наслаждайтесь жизнью.
11. Побольше размышляйте о себе.
12. Восхваляйте или демонизируйте свое прошлое.
13. Стройте отношения с кем-то, кого вы хотите изменить.
14. Критикуйте.
moose, transparent

о конкурсах красоты

СЯУ что-то, о чем сам бы не догадался: оказывается, в Америке популярность конкурсов красоты катастрофически упала с начала 80-х, равномерно, по причинам, которые мне не очень понятны. Возможно, и во всем мире так же (исключая всплески там, где это внове, типа СССР после распада)? 



Я узнал это из обсуждения новости о том, что в конкурсе Мисс Америка решили отказаться от оценки участниц в купальниках, и собираются привлечь "больше участниц всех размеров". В свете падающего количества зрителей, впрочем, это выглядит, возможно, как попытка утопающего ухватиться за какую-то ветку (представительница конкурса ссылается на #MeToo, например).Рейтинг мисс Америка за последние годы (в зрителях, а не домах, как на картинке):

2013: 8.6 million viewers
2014: 7.1 million viewers
2015: 7.9 million viewers
2016: 6.25 million viewers
2017: 5.6 million viewers

(данные из этой ветки)
moose, transparent

танцующие ссылки

СЯУ из комментария в Hacker News, что проблему решения судоку можно легко представить в виде частного случая проблемы exact cover. Заодно решил прочитать уже ставшую классической статью Кнута о его алгоритме "танцующих ссылок" для решения проблемы exact cover.

Помню, что мне много лет назад это показалось слишком сложным, и я отложил статью, но теперь не понимаю, почему. На самом деле эти танцующие ссылки не сложны, и действительно очень красивы. Рекомендую к прочтению.

Если в двух словах, то Кнут описывает эффективный подход к написанию поиска с backtracking. Любой, кто писал в том или ином виде backtracking search, знает, что сложность обычно заключается в том, чтобы выбрать правильную репрезентацию данных, так, чтобы добавить следующий выбор, а потом его "откатить назад", было легко. Часто оказывается, что есть трейдофф между быстрым доступом к данным и быстрым изменению/откатыванию их части. Алгоритм Кнута основывается на следующем наблюдении. Если мы удаляем элемент из двойного связанного списка, то сам элемент, вырванный из списка, естественным образом сохраняет в себе - в своих указателях влево/вправо - информацию о том, где он был в списке; и за O(1) времени его можно обратно вставить. Значит, если в процессе backtracking search можно представить "следующий выбор" как удаление элементов из связанных списков, то "откат" - возвращение их в эти списки - получается и очень быстрым, и удобным с точки зрения промежуточных данных: элементы сами помнят, куда их вставлять, не нужно это отдельно никуда записывать.

Это еще не все, есть важные подробности конкретно в случае exact cover о том, в каком порядке удалять/возвращать элементы из списков, но это все можно прочитать в статье. Отличная статья, легко читается.

Мета-замечание: "алгоритм танцующих ссылок" Кнута требует свободного владения указателями! Не в каком-то конкретном языке, а самим понятием указателя. Его можно считать примером того, почему все-таки важно программистам иметь опыт работы с языками, в которых указатели не спрятаны от программиста: не только Питон, но и C++ или хотя бы Джава. Не то чтобы на Питоне невозможно было имплементировать этот алгоритм; нет, можно, но странно и неудобно, потому что нормальный способ работы со списком в Питоне - это, как ни странно, питоновский список, а в нем удаленный элемент не хранит при себе свое место и не может за O(1) вернуть себя на него.

Кто-то написал элегантный код алгоритма Кнута на Питоне, но его можно считать только кодом алгоритма X для решения exact cover, а не питоновским вариантом "танцующих ссылок", вопреки тому, что говорит автор кода. В его коде никакие ссылки не танцуют, а удаление элемента и возвращение его воплощено как удаление/возвращение из питоновского множества, т.е. операция O(logN) на каком-то сбалансированном дереве (полагаю - не знаю точно, как в Питоне внутри устроены множества). С другой стороны, важно отметить, что если это работает для проблем нужного нам масштаба, то и ладно. Еще в начале 90-х, не говоря уж о более ранних эпохах, делать отдельное сбалансированное дерево для каждой строки матрицы было бы безнадежно медленным. Закон Мура быстро, но верно сделал свое дело. Задачи с малым N теперь обычно не требуют элегантных оптимизаций, подобных "танцующим ссылкам"; а задачам с огромным N они все равно часто не помогают, потому что задачи NP-полные и перебор растет экспоненциально. Остается область посредине, где такие техники все еще важны и останутся важными. Нередко интересные задачи оказываются именно там, так что "танцующие ссылки" еще потанцуют, думаю.
moose, transparent

велосипедное

Неожиданное и очень элегантное жанровое оформление для велосипедного видео:



Это тот же Danny MacAskill, который несколько лет назад опубликовал вот это видео, от которого я лично тогда просто охренел. До сих пор его иногда пересматриваю.
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

о глупости



Супруга игрока футбольного клуба «Анжи» Инна ЖИРКОВА официально отказалась от титула «Миссис Россия», который она завоевала в прошлом году. Кроме того Жиркова решила не участвовать в предстоящем конкурсе красоты.

Свое решение Инна объясняет тем, что после нашумевшего в Интернете телеинтервью журналисту Борису Соболеву она впала в депрессию и разочаровалась в конкурсах.


Бредовая какая-то история. Тысячам гегекающих блоггеров приятно издеваться над женщиной, которую самодовольный мудак-журналист выставил дурочкой, смонтировав несколько ответов из интервью.

Ах, она сказала, что Солнце вращается вокруг Земли. 99% взрослого населения планеты не могут объяснить, откуда берутся времена года (чтобы не было иллюзий - я включаю себя в это число [1]), или почему, если Земля вращается вокруг Солнца, она на него не падает. Такая ли уж большая разница от этих вопросов до того, кто вокруг кого вращается?

Я почти целиком согласен с этой записью, кстати. Почти целиком - потому что не могу идентифицироваться с "в школе мы таких [как этот журналист] тупо пиздили". Но вот то, что журналист этот - самодовольный мудак, и этот тип его мудачества прочитывается мгновенно за пять секунд после начала видео - это несомненно. И все остальное там верно, включая особенно
Еще не очень понятны сами причины для возмущение и возбуждения. Она не чиновник, не госслужащий, и даже не депутат Госдумы. Она не вмешивалась в наши/ваши дела, не навязывалась, не пыталась учить нас жизни. Она не лезет в телеведущие, в политику, не агитирует за путина, не гвоздит Госдеп. Она – НЕ Света из Иванова, агрессивная в своем невежестве. Она просто приняла участие в каком-то левом конкурсе красоты, победила там и в результате попала на карандаш к мудаку с канала ВГТРК. Все.
Именно так. Есть невежество, а есть агрессивное невежество, и только агрессивное невежество (которого у Жирковой нет вообще, зато у тех, кто над ней издевается - полно) заслуживает высмеивания.

[1] Я поймал себя на том, что не знаю, откуда берутся времена года, а думаю по этому поводу какую-то херню, будучи взрослым человеком с университетским образованием. Это было много лет назад, и сейчас я лучше смогу ответить на этот вопрос, но это в большой мере случайный результат, который не дает мне никаких оснований смотреть свысока на тех, кто не знает.
moose, transparent

мимоходом

В книжном магазине бросил взгляд на полку французских книг и удивился нескольким примерам того, что не переводят название. Роман Джонатана Франзена "Freedom" во французском переводе называется... "Freedom". Еще один пример - "Summer and the City" Кэндэс Бушнелл.

Мода, что ли, такая пошла?