?

Log in

No account? Create an account
танцующие ссылки - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

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

Links
[Links:| English-language weblog ]

танцующие ссылки [июл. 18, 2015|12:28 am]
Anatoly Vorobey
[Tags|]

СЯУ из комментария в 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-полные и перебор растет экспоненциально. Остается область посредине, где такие техники все еще важны и останутся важными. Нередко интересные задачи оказываются именно там, так что "танцующие ссылки" еще потанцуют, думаю.
СсылкаОтветить

Comments:
[User Picture]From: occuserpens
2015-07-18 12:40 am
[Кто-то написал элегантный код алгоритма Кнута на Питоне, но его можно считать только кодом алгоритма X для решения exact cover, а не питоновским вариантом "танцующих ссылок", вопреки тому, что говорит автор кода. В его коде никакие ссылки не танцуют, а удаление элемента и возвращение его воплощено как удаление/возвращение из питоновского множества, т.е. операция O(logN) на каком-то сбалансированном дереве (полагаю - не знаю точно, как в Питоне внутри устроены множества). С другой стороны, важно отметить, что если это работает для проблем нужного нам масштаба, то и ладно.]

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

(Ответить) (Thread)
[User Picture]From: _winnie
2015-07-18 03:04 am
1) set и dict в питоне - это хеш-таблицы (с плохой хеш-функцией).
https://github.com/python-git/python/blob/master/Objects/dictobject.c


2) А чем лучше всего читать ps-файлы? Я скачал ghostscript, проблевался (от жуткого рендера шрифтов и я не понял как посмотреть что-то кроме первой страницы, но я не буду узнавать как листать документ командами в консоли!!!), нашёл онлайн-конвертилку ps в pdf, но вдруг какая-то программа может нормально показывать ps после дабл-клика по нему. Может какой-то плагин к Foxit/Acrobat reader.

Edited at 2015-07-18 03:04 (UTC)
(Ответить) (Thread)
[User Picture]From: nefedor
2015-07-18 03:10 am
Чем плоха питоновская хеш-функция?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: occuserpens
2015-07-18 03:14 am
Эээ, а причем тут ps?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: ak_47
2015-07-18 03:47 am
Статью Кнута можно тут в PDF посмотреть: https://arxiv.org/abs/cs/0011047 Там справа вверху есть линк на документ.

но вдруг какая-то программа может нормально показывать ps после дабл-клика по нему

Вроде Acrobat Reader умеет, но я им уже давно не пользуюсь, поэтому на 100% не уверен.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: avva
2015-07-18 10:03 am
2) gsview чтобы читать ps. Я заменил ссылку на PDF в arxiv.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: lyuden
2015-07-18 05:09 am
Как Питонисту со стажем приятно видеть, что Питон начал использоваться как стандартный мальчик для битья.

"Сначала они тебя не замечают, потом смеются над тобой, затем борются с тобой. А потом ты побеждаешь."

Так победим.


По сути.

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

ибо простейший двухсвязный список на питоне


l=[]
r=[]
c=[l,r]
l.extend([None,c])
r.extend([c,None])

И все.
(Ответить) (Thread)
[User Picture]From: dreamer_other
2015-07-18 06:04 am
И какой оверхед по памяти на каждый элемент списка?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: gegmopo4
2015-07-18 07:41 am
В Питоне это часто не нужно. Большинство задач, решаемых двусвязными списками в других языках программирования, в Питоне удобнее, проще и эффективнее решать по-другому. Ведь динамический массив и хештаблица — примитивы в Питоне (да и deque под рукой). Случаи, когда нужен именно двусвязный список, редки (в самой стандартной библиотеке Питона они используются в реализации OrderedDict, lru_cache, и… пожалуй всё).
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: occuserpens
2015-07-18 10:27 am
pool = {
0: [None, 1, "who"],
1: [0, 2, "cares"],
2: [1, 3, "about"],
3: [2, None, "https://en.wikipedia.org/wiki/MMIX"]
}

Потом это сериализируется в Json и читается на Фортране :)

Edited at 2015-07-18 10:30 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: atanvarnoalda
2015-07-18 06:11 am
О, именно этот код алгоритма Кнута я и использовал для решения своей головоломки, которую описывал в прошлом году у себя в ЖЖ. Надеюсь, скоро напишу следующую чатсь, где именно об этом алгоритме и рассказывается.
К сожалению, решение получилось слишком медленным... выдавало пару десятков решений в час, тогда как их общее количество явно немногим меньше гугола...

Edited at 2015-07-18 06:11 (UTC)
(Ответить) (Thread)
[User Picture]From: onodera
2015-07-18 10:47 am
Вместо "имплементировать" лучше писать "реализовать".
(Ответить) (Thread)
[User Picture]From: gdy
2015-07-19 08:30 pm
воплотить)
(Ответить) (Parent) (Thread)
[User Picture]From: hyperpov
2015-07-19 12:47 pm
Прикольно. Как-то я написал решение судоку на питоне в порядке развлечения, только не знал, что об этом целая наука есть. В случае судоку все сбалансированные деревья, которые живут в недрах интерпретатора, имеют ограниченный (и весьма небольшой) размер, поэтому там вопрос о скорости роста непринципиален. На C++, конечно, работало бы еще быстрее, но зато писанины больше.
(Ответить) (Thread)
[User Picture]From: e2pii1
2015-07-21 09:49 am
На C++ c STL - сильно больше писанины ?
(Ответить) (Parent) (Thread)