July 18th, 2015

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

можно раздавать людям просто белые листы

Интересный репортаж в "Медузе" о российских журналистах, которые уехали работать на Украину.

Айдер Муждабаев, бывший заместитель главреда в "Московском Комсомольце", зажигает:
В определенный момент у меня на работе начал ум за разум заходить. Когда коллеги рассказывают, как «наши» в Донецке бьют «бандеровцев», что «Боинг» сбили укропы, а воинам АТО выдают рабов, возмущаться этому просто нет смысла — тебя не поймут; а слушать это постоянно — вредно для психики.

В России установилось примерно такое же равновесие, какое было в Германии в 1938–1939 годах: когда гестапо уже почти некого было сажать, потому что все были согласны с линией партии. Непонятно, для кого там теперь журналисты работают. Мне показалось, что я занимаюсь в определенном смысле мартышкиным трудом, объясняя одним людям то, что они и так знают, а другие все равно не хотят слушать. Это такой медийный цугцванг — каждый шаг хуже предыдущего. Можно уже перестать выпускать газеты, а раздавать людям просто белые листы, и каждый поймет свое, потому что сейчас речь идет уже не об информации, а об убеждениях. Ты им, грубо говоря, хоть похоронку на сына принеси, они все равно скажут, что так правильно, потому что это хорошо для «русского мира».

Так что сегодня в России журналисту — я, конечно, утрирую — делать особо нечего. Лично для меня сейчас важнее, чтобы у крымских татар были свои независимые медиа, нежели переживания о 146-миллионной стране, в которой 120 миллионов не желают знать никакой объективной информации вообще. Это, скорее, не общество, а клиническое отделение патриотической паранойи. Не знаю, что тут [в Киеве] со мной будет, но по-человечески считаю, что правильно сделал. Для организма полезнее даже быть нищим в Киеве, чем главным редактором в Москве.
moose, transparent

мимоходом

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

Боже мой, как же это здорово. Я забыл, как это прекрасно. Я иду по улице, и у меня нет при себе интернета. Захожу в спортзал - без интернета. Сижу за столиком в кафе с книжкой (электронной, понятно - без фанатизма) - и нет интернета!

Как только найду телефон или куплю новый - первым делом отключаю интернет.
moose, transparent

мимоходом

Юля смотрит мультики про Тома и Джерри, много подряд. После четвертого или пятого откидывается на стуле, грустно вздыхает и разочарованным голосом говорит в пространство:

— Том никогда не станет добрым.