Кратко — как работает поиск
- Prolog использует SLD-резолюцию: лево‑древесный, глубинный поиск с созданием choice‑points (точек выбора) на каждом месте с несколькими подходящими правилами/разрешениями. При неудаче система откатывается (backtracks) к последнему choice‑point и пробует следующий вариант. Повторяет, пока не найдёт ответ(ы) или не исчерпает варианты. При использовании cut (!) вырубается часть дерева поиска.
Почему это плохо для производительности
- Комбинаторный взрыв: если на каждом шаге в среднем ветвление b и глубина решения d, число обзоров может расти как $\mathcal{O}(b^d)$.
- Плохой порядок правил/целей: Prolog пробует правила и цели слева направо; если сначала стоит дорогостоящая/недетерминированная проверка, которая редко отбрасывает ветви, много лишнего поиска будет проведено.
- Недостаточная индексация: большинство реализаций индексируют только первый аргумент; если он не инстанцирован, выбор подходящих клауз может быть линейным по числу клауз: $\mathcal{O}(n)$.
- Повторные вычисления перекрывающихся подзадач (отсутствие мемоизации) — дублирование работы.
- Неэффективные структуры (напр., многократное использование append/2 на больших списках) и ненужная генерация промежуточных решений приводят к большому количеству backtrack’ов.
- Нерациональная рекурсия (нехвостовая) увеличивает стек и время.
Как реорганизовать программу для ускорения (практические приёмы)
1. Поменять порядок целей в теле правила:
- Сначала ставьте селективные/детерминированные тесты (арифметика, ground/var/type, простое унифицирование), затем дорогие/рекурсивные. Это резко уменьшает число создаваемых ветвей.
2. Порядок клауз (правил):
- Ставьте наиболее вероятные/быстрые клаузы первыми, чтобы получить успех без большого backtracking’а.
3. Использовать индексацию:
- Делайте дискриминирующий аргумент первым; при необходимости используйте специализированные предикаты или предобработку данных. В некоторых реализациях можно включить расширенную индексацию.
4. Обрезание деревьев поиска:
- Применяйте cut (!) осторожно (green cut — для оптимизации без изменения логики); где нужно — once/1, ! после детерминированного успеха.
5. Мемоизация / таблирование:
- Если есть перекрывающиеся подзадачи (динамическая программирование), используйте tabling (XSB, SWI-Prolog tabling) или явное кеширование результатов.
6. Использовать эффективные структуры:
- Разница‑списки для частых конкатенаций, аккумулирующие параметры для хвостовой рекурсии.
7. Сделать рекурсию хвостовой:
- Переписать предикаты с аккумуляторами, чтобы компилятор мог оптимизировать стек.
8. Отбрасывать варианты как можно раньше:
- Например, проверка посетили ли уже узел в поиске пути должна стоять до рекурсивного вызова.
9. Использовать ограничения/CLP:
- В задачах с числовыми ограничениями часто CLP(FD) или другие constraint‑решатели быстрее, т.к. они отсеивают невозможные ветви заранее.
10. Профилирование и тестирование:
- Запустить профайлер Prolog, искать горячие точки (часто вызываемые/длительные предикаты) и реорганизовать их.
Короткий пример (смысловой): если у вас было
p(X) :- expensive(X), cheap_test(X).
лучше написать
p(X) :- cheap_test(X), expensive(X).
тогда многие X отсеются на cheap_test без дорогих вызовов.
Итог: минимизируйте армию ненужных choice‑points — ставьте селективные/информационные проверки раньше, используйте индексацию и таблирование, превращайте рекурсии в хвостовые, и только после измерений используйте cut/оптимизации.