Эффективность программ на Прологе.
В практическом программировании на Прологе необходимо обращать внимание на эффективность программ. Установим критерии оценки программ. Основной оцениваемый параметр число выполняемых унификаций и число попыток унификации в процессе вычисления. Этот параметр связан с временем работы программы. Ещ один параметр глубина вложенной рекурсии. Если в процессе вычислений глубина станет больше максимально допустимой, то вычисления прервутся.
На практике эта проблема является основной. Третий параметр число порожднных структур данных. Рассмотрим последовательно эти параметры. Можно предположить, что при разумной записи детерминированного последовательного алгоритма в виде программы на Прологе ожидаемая эффективность алгоритма сохранится. Обычно результирующие программы на Прологе не основываются на унификациях общего вида или глубоких возвратах. Сложности могут возникнуть при реализации алгоритмов, связанных с существенной перестройкой структур данных, например используя деревья, при этом затраты будут возрастать логарифмически.
Однако во многих случаях более естественно было бы модифицировать сам алгоритм, приспосабливая его к принципу однократного присваивания, присущему логическим переменным. Для указанных алгоритмов применимы обычные методы анализа сложности вычислений. Если не используется полная унификация, то можно показать, что время выполнения редукции цели с помощью предложения программы ограничено константой.
Величина константы зависит от программы. Поэтому число выполняемых в программе редукций, как функция от размера е входа, является хорошей оценкой временной сложности программы. При программировании на Прологе средства, представляемые языком, могут использоваться полностью. Можно писать недетерминированные программы и программы, использующие полную унификацию. Анализ сложности таких программ представляет собой трудную задачу и требует оценки затрат на просмотр при поиске и размера унифицируемых термов.
Один из основных способов повышения эффективности программ совершенствование алгоритма. Хотя речь идт о декларативном языке, понятие алгоритма в Прологе остатся тем же, что и в других языках программирования. Помимо выбора наиболее удачного алгоритма можно использовать ещ несколько способов для увеличения эффективности программ на Прологе. Один из них состоит в выборе наилучшей реализации. Эффективная реализация характеризуется исходной скоростью, возможностью индексирования, применением оптимизации остатка рекурсии и методом сборки мусора. Единицей измерения скорости выполнения программы на языке логического программирования обычно служит LIPS число логических выводов в секунду.
При вычислениях логический вывод соответствует редукции. 2.4.2.