Временная сложность Пролога лучше, чем наивный перебор?

Наивный поиск методом перебора останется наивным перебором, когда он буквально переведен на Prolog.

Это нормально: Plain Prolog очень хорошо подходит для описания и выполнения поиска методом грубой силы. Тем не менее, вы, вероятно, не сможете превзойти оптимизированную вручную низкоуровневую версию любого поиска методом грубой силы с помощью поиска грубой силы, написанного на Прологе. С другой стороны, Prolog настолько прост и удобен для набора, что вы, вероятно, скоро найдете лучшие стратегии поиска с небольшим прототипированием, и эти другие стратегии часто легко превзойдут любую реализацию грубой силы огромным допуск. И даже при наивном переводе Пролог довольно хорош в отслеживании с возвратом и делает это эффективно в пределах некоторого (меньшего или большего, в зависимости от используемой вами реализации Пролога) фактора низкоуровневого кода.

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

Обещание ограничений, и это обещание в значительной степени превратилось в реальность, состоит в том, что (1) вы формулируете требования и (2) движок Prolog находит решение за вас. Посмотрите clpfd для одного очень важного примера этой схемы. .

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

В Прологе ответ часто бывает: Очень просто. На большинстве других языков не так много.

Если вы просите решить что-нибудь, определенно есть проблемы, которые Prolog решает за линейное время. Например, следующий предикат append/3:

append([H|A],B,[H|R]) :-
    append(A,B,R).
append([],L,L).

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

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

Вопрос в вашем вопросе, похоже, заключается в том, что если я напишу код, подобный Prolog, на Scheme, будет ли он работать хуже, чем если я напишу Prolog на Prolog?

Однозначного ответа нет. На самом деле та часть вашей проблемы, которая хорошо отображается на Prolog, вероятно, будет работать хуже, чем в Prolog. Почему? Потому что все встроенные функции Prolog написаны на Prolog, а все ваши встроенные функции написаны на Scheme. Как @CommuSoft указывает на append/3, реализация встроенных функций Prolog может использовать сильные стороны Prolog. В этих краях вам предстоит нелегкая битва. Кроме того, имеющиеся у нас реализации Пролога достаточно стары, чтобы мы десятилетиями работали над улучшением производительности унификации, потому что это интересная область здесь.

В то же время, большинство важных программ Prolog в конечном итоге заканчиваются некоторыми процедурными элементами. Эти биты, вероятно, неконкурентоспособны с C или Scheme, потому что их не так интересно оптимизировать, и какие бы исследования ни проводились по этому поводу, вместо этого проводились в Scheme и ML. Так что вы выиграете в этих областях.

Как пользователь Scheme, я думаю, что вам будет выгоднее писать программы в стиле Scheme: функциональный, с примесью макросов, чтобы придать им декларативный вид. Если у вас есть проблема, которая до неприличия хороша для Prolog, вы всегда можете использовать miniKanren, но держите ее подальше от остальная часть вашей программы. Пусть ваш язык будет вашим языком.

Я не согласен с @ahuemmer по поводу C и Prolog только потому, что труд ограничен, а программы имеют много аспектов помимо производительности. Стоимость авторства C намного выше, поэтому вы будете усерднее использовать более плохие стратегии и в конечном итоге получите менее гибкий код. Даже если вы ограничите пространство проблемы чем-то небольшим и четко определенным, у программиста Prolog будет больше времени, чтобы поэкспериментировать и найти лучшее решение, возможно, с большей временной сложностью. Если мы говорим о неограниченном объеме труда, версия C, вероятно, превзойдет первую версию Prolog. Но нужно учитывать все размеры.

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

Чистый Пролог (без оператора «вырезать» или императивных функций) выделяется в одном отношении: для определенного класса проблем это «процедура полного опровержения». Если проблема не имеет решения, программа Prolog завершит свою работу и сообщит об отсутствии решения. С другой стороны, если у проблемы есть решения, программа может не найти ни одного, некоторых или всех и не завершиться.

Если вы используете императивные функции или сокращения, все ставки отключены.

Prolog может иногда обрабатывать проблемы с бесконечным количеством ответов, если ответы имеют правильный тип шаблона.

ИМХО, это зависит от проблемы. Если это действительно разрешимо только с помощью грубой силы и поиска с возвратом, я не думаю, что (даже идеализированный «лучший») Prolog был бы быстрее, чем e. г. хорошо написанная программа на C.

С другой стороны, если у вас есть такая проблема, для решения которой Prolog может использовать свою базу данных и дедуктивный подход (то есть, не обязательно с возвратом грубой силы), она может иметь лучшую производительность, чем другая программа поиска с возвратом грубой силы.

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