Цель 2 преимущества логического программирования 4
Эффективность программ на Прологе
жүктеу/скачать 36,6 Kb.
|
Эффективность программ на Прологе.В практическом программировании на Прологе необходимо обращать внимание на эффективность программ. Установим критерии оценки программ. Основной оцениваемый параметр – число выполняемых унификаций и число попыток унификации в процессе вычисления. Этот параметр связан со временем работы программы. Ещё один параметр – глубина вложенной рекурсии. Если в процессе вычислений глубина станет больше максимально допустимой, то вычисления прервутся. На практике эта проблема является основной. Третий параметр – число порождённых структур данных. Рассмотрим последовательно эти параметры. Можно предположить, что при разумной записи детерминированного последовательного алгоритма в виде программы на Прологе ожидаемая эффективность алгоритма сохранится. Обычно результирующие программы на Прологе не основываются на унификациях общего вида или глубоких возвратах. Сложности могут возникнуть при реализации алгоритмов, связанных с существенной перестройкой структур данных, например используя деревья, при этом затраты будут возрастать логарифмически. Однако во многих случаях более естественно было бы модифицировать сам алгоритм, приспосабливая его к принципу однократного присваивания, присущему логическим переменным. Для указанных алгоритмов применимы обычные методы анализа сложности вычислений. Если не используется полная унификация, то можно показать, что время выполнения редукции цели с помощью предложения программы ограничено константой. Величина константы зависит от программы. Поэтому число выполняемых в программе редукций, как функция от размера её входа, является хорошей оценкой временной сложности программы. При программировании на Прологе средства, представляемые языком, могут использоваться полностью. Можно писать недетерминированные программы и программы, использующие полную унификацию. Анализ сложности таких программ представляет собой трудную задачу и требует оценки затрат на просмотр при поиске и размера унифицируемых термов. Один из основных способов повышения эффективности программ – совершенствование алгоритма. Хотя речь идёт о декларативном языке, понятие алгоритма в Прологе остаётся тем же, что и в других языках программирования. Помимо выбора наиболее удачного алгоритма можно использовать ещё несколько способов для увеличения эффективности программ на Прологе. Один из них состоит в выборе наилучшей реализации. Эффективная реализация характеризуется исходной скоростью, возможностью индексирования, применением оптимизации остатка рекурсии и методом сборки мусора. Единицей измерения скорости выполнения программы на языке логического программирования обычно служит LIPS – число логических выводов в секунду. При вычислениях логический вывод соответствует редукции. жүктеу/скачать 36,6 Kb. Достарыңызбен бөлісу:
|