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

[avva]

СЯУ из комментария в 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

[occuserpens.livejournal.com]

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

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

[http://users.livejournal.com/_winnie/]

1) set и dict в питоне - это хеш-таблицы (с плохой хеш-функцией).
https://github.com/python-git/python/blob/master/Objects/dictobject.c


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

[nefedor.livejournal.com]

Чем плоха питоновская хеш-функция?

[http://users.livejournal.com/_winnie/]

afaik, в хеш-таблицах нет перехеширования (возможно, в python3 надо перепроверить), и вот такая хеш-функция напрямую используется как номер корзины в хеш-таблице, после округления по модулю размеры числа корзин:
hash(1) = 1
hash(2) = 2
hash(3) = 3


А вот таким значениям хеш-функции не поможет даже перехеширование (пользователи 64-битных питонов - могут добавить 8 нулей в середине для того же эффекта):
>>> hash(0x100000009)
10
>>> hash(0x200000008)
10
>>> hash(0x300000007)
10
>>> hash(0x400000006)
10

[nefedor.livejournal.com]

Ну, на любую хеш-функцию можно найти примеры коллизий, и о чем это говорит?
Что касется перехэширования, то если я правильно понимаю смысл этого термина, то оно происходит всякий раз когда достигается определенное число коллизий в хэш-таблице.

[http://users.livejournal.com/_winnie/]

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

Под "перехешированием" я понимал как применение дополнительной второй хеш-функции к тому, что пришло из hash()

[nefedor.livejournal.com]

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

Понятно, а зачем это нужно? Если из первого hash() пришло два одинаковых значения, то очевидно второй hash() каким бы он ни был не сделает их разными, разве нет?
В применении же к конкретной специфике построения словаря на хэш-таблице, хэширование просто меняется в зависимости от количества данных - мы периодически меняем действительную адресацию по корзинам. Да, при этом все что хэшится к небольшим значениям будет продолжать хэшиться к ним же, однако не думаю что в практических задачах реально может встретиться слишком много подобных данных (хотя на этом можно построить DDoS атаку: https://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf, но кажется они что-то изменили в алгоритме хеширования в 2012м: http://bugs.python.org/issue13703).
Наконец, можно заимплементить свой собственный __hash__() если встроенный не нравится - ибо питон динамический.
Подробнее:
http://stackoverflow.com/questions/13514716/overriding-pythons-hashing-function-in-dictionary
и еще подробнее:
http://www.laurentluce.com/posts/python-dictionary-implementation/

[occuserpens.livejournal.com]

Эээ, а причем тут ps?

[http://users.livejournal.com/_winnie/]

Статья Дональда Кнута - в ps. http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz

Получается вот такое юзабилити:

Скачиваем файл. Даблкликаем по файлу в списке скачанного. Открывается WinRar. Разархивируем документ в какую-нибудь папку. Ищем в гугле конвертилку. Закачиваем в конвертилку файл, указывая тот путь, по которому его разархивировали.

pdf: кликаем на ссылку, сразу читаем (вариант: кликаем на ссылку и скачиваем, кликаем по скачанному и читаем в установленной читалке pdf).
http://dobrokot.ru/dump/donald-knuth-dancing-links-colors.pdf

[leontodys.livejournal.com]

Попробуй https://wiki.gnome.org/Apps/Evince
Под линукс рендерит вполне годно

[occuserpens.livejournal.com]

https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

[lyuden.livejournal.com]

Linux master race

Клик на ссылку -файл скачался. Клик на скачанный файл в панели хрома - открывается статься.

[kot-ivanovich.livejournal.com]

Стенфорд любит притворяться, что виндов не существует в природе :) От меня лично ему за это пламенный респект, я тоже люблю так притворяться.

ps

[leontodys.livejournal.com]

Так статья же в ps, это более-менее родной формат в который компилируются TeX документы.

[ak_47]

Статью Кнута можно тут в PDF посмотреть: https://arxiv.org/abs/cs/0011047 Там справа вверху есть линк на документ.

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

Вроде Acrobat Reader умеет, но я им уже давно не пользуюсь, поэтому на 100% не уверен.

[avva.livejournal.com]

Спасибо, заменю ссылку сейчас.

[avva.livejournal.com]

2) gsview чтобы читать ps. Я заменил ссылку на PDF в arxiv.

[http://users.livejournal.com/_winnie/]

Спасибо!


( gsview замыливает буквы из-за проблем совместимости старых программ с высоким DPI монитора, но это не мешает читать сложную статью )

[dmytrish.livejournal.com]

Preview/Evince/Okular?

[igde.livejournal.com]

Sumatra PDF при установленном ghostscript умеет читать ps-файлы. Довольно удобно.

[lyuden.livejournal.com]

Как Питонисту со стажем приятно видеть, что Питон начал использоваться как стандартный мальчик для битья.

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

Так победим.


По сути.

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

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


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

И все.

[dreamer-other.livejournal.com]

И какой оверхед по памяти на каждый элемент списка?

[lyuden.livejournal.com]

Про оверхед питоновского списка по сравнению с С шным указателем на область памяти ?

ну интерпретатор говорит, что переменная с говорит занимает 88 байт.
Tuple можно зафигачить на 72 байта.

В C/C++ это два 8 байтовых указателя. Т.е. оверхед где то в 4-6 раз если грубо

Оверхед конечно является аргументом, против Питона, но я то отвечал не на это. Я отвечал на утверждение, что ссылки на питоне выглядят странно. Как указывает автор поста - оверхед уже не так важен.

Сейчас, часто для интересных задач данные в оперативную память в принципе уже не влезают и надо уже использовать кластеры и там задержка по сети уже часто нивелирует любое преимущество в скорости. Хоть на Ruby пиши.

А скорость в разработке,часто нивелирует требование по памяти ибо железо дешевле времени программистов.

[gegmopo4.livejournal.com]

В Питоне это часто не нужно. Большинство задач, решаемых двусвязными списками в других языках программирования, в Питоне удобнее, проще и эффективнее решать по-другому. Ведь динамический массив и хештаблица — примитивы в Питоне (да и deque под рукой). Случаи, когда нужен именно двусвязный список, редки (в самой стандартной библиотеке Питона они используются в реализации OrderedDict, lru_cache, и… пожалуй всё).

[lyuden.livejournal.com]

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

[gegmopo4.livejournal.com]

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

[lyuden.livejournal.com]

Ну я вроде написал, что я питонист со стажем и я тащемта это знаю. В общем, насколько я понял с моим комментарием все ок. Так что предлагаю замять для ясности.

[gegmopo4.livejournal.com]

Моё возражение касается утверждения, что человек в примере поленился сделать двухсвязный список. Пример получился коротким и очень простым. С двусвязным списком вышло бы дольше, менее читаемо, и возможно менее эффективно.

[lyuden.livejournal.com]

Он реализовал двухсвязный список в этом примере ?

Если да. То спорьте с автором поста, не со мной.

> возможно менее эффективно

Очевидно, нет. На достаточно больших данных, танцующие ссылки победят. Да и по опыту, set достаточно тормознутый тип данных на больших объемах.

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

Но я же вообще говорил не про это.

[occuserpens.livejournal.com]

pool = {
0: [None, 1, "who"],
1: [0, 2, "cares"],
2: [1, 3, "about"],
3: [2, None, "https://en.wikipedia.org/wiki/MMIX"]
}

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

[atanvarnoalda.livejournal.com]

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

[onodera.livejournal.com]

Вместо "имплементировать" лучше писать "реализовать".

[gdy.livejournal.com]

воплотить)

[hyperpov.livejournal.com]

Прикольно. Как-то я написал решение судоку на питоне в порядке развлечения, только не знал, что об этом целая наука есть. В случае судоку все сбалансированные деревья, которые живут в недрах интерпретатора, имеют ограниченный (и весьма небольшой) размер, поэтому там вопрос о скорости роста непринципиален. На C++, конечно, работало бы еще быстрее, но зато писанины больше.

[e2pii1.livejournal.com]

На C++ c STL - сильно больше писанины ?