3.6. Увеличение скорости и эффективности программ

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

1. При определении возраста частота применения тех или иных правил зависит от того, чей возраст определяется.
2. Последовательность размещения выводимых на печать результатов не совпадает с последовательностью размещения информации в базе данных.
3. Последовательность размещения результатов может измениться, если изменится текущая дата. Проверить это достаточно просто; для этого необходимо следующим образом выбирать текущую дату: сначала она должна предшествовать дате какого-нибудь дня рождения, затем совпадать с ней и, наконец, следовать за ней. Но учтите, что в каждый момент времени в базе данных должна находиться только одна дата.
4. Последовательность размещения результатов изменится, если поменять местами первое и второе утверждения отношения age.

Значительно большими диагностическими возможностями обладают специальные программы трассировки, входящие в состав системы программирования мицроПролог. Максимально возможную информацию обеспечивает, например, программа SIMTRACE. Поскольку для этой программы требуется довольно много памяти, перед ее использованием удалите из памяти все, что там было, и введите программу, приведенную ниже.

Betty born (3 5 1950)

X LESS Y date now (22 9 1985)

Тестовый запрос для этой программы и ответы на него будут выглядеть так:

all (x у: х age у)

No (more) answers

Даты рождения людей выбраны таким образом, чтобы они не посредственно предшествовали и следовали за текущей датой - (22 9 1985). Это будет гарантировать участие в обработке запроса всех правил. После того как у Вас появилась уверенность в правильности программы, удалите из памяти модули program-mod и errmess-mod с помощью команды KILL. Затем используйте команду LOAD для того, чтобы загрузить на свободное место программу трассировки SIMTRACE. В том случае, если памяти все же окажется недостаточно, попробуйте удалить из модуля query-mod любые из следующих отношений: which, all, one, is, lood, save, +, -, %, @, *, CONS, reserved, true-of и defined.

Естественно, после этого использовать в запросах те отношения, которые Вы удалили, будет нельзя. Для того чтобы получить полную информацию о процессе обработки запроса, введите

Ниже приведен протокол диалога между пользователем и ЭВМ:

& all-trace (x yi x age у)

[(2 1) : текущая дата (X Y Z) трассировка?]

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

Используемые во время трассировки утверждения и условия -помечаются номерами, заключенными в скобки. Например, (1 1) - первое утверждение в первом условии, (2 1) - второе утверждение в первом условии и т. д. Для предложений сложной структуры потребуется более двух номеров. Например, (1 3 1) - первая часть третьего утверждения в первом условии; в данном случае такой номер появляется, когда анализируется конструкция (either ... or...).

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

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

(4 1). Здесь поиск альтернатив для SUM (X 1950 1985) сразу же заканчивается неудачей, поскольку существует единственное значение X, для которого справедливо

(2 1). Здесь производится попытка найти отличный от (22 9 1985) список (X Y Z), который содержится в предложении вида

Эта попытка также заканчивается неудачей, так как такой список только один - (22 9 1985). Но если было бы введено несколько предложений, определяющих отношение date now, то все они использовались бы для поиска решений, связанных с определением возраста Бетти.

(3 1). Здесь ищется альтернативное решение для первой части конструкции (either ... or...).

Несколько слов необходимо сказать о том, как использование отношения "/" позволяет увеличить эффективность обработки запроса. Переход к отношению "/" означает, что возврат ко всем предшествующим условиям, сопоставление которых прошло успешно, запрещен. Кроме того, что также очень важно, ни одно из условий, стоящих после "/", в тех случаях, когда условия, предшествующие "/", доказаны, не анализируется. Пока в качестве главной причины неэффективности нашей программы можно отметить следующее: пытаясь ответить на запрос X age Y, программа каждый раз осуществляет сопоставление

с соответствующим предложением программы и постоянно используется возврат для поиска альтернативных дат, которых заведомо нет. Это в принципе не слишком опасно, поскольку приводит к неудаче только один раз. Гораздо серьезнее следует относиться к возврату, который возникает в тех случаях, когда часть проверяемых условий удовлетворяется^*. Отметим желательность выполнения какой-то операции, позволяющей программе оптимально организовывать доступ к текущей дате.

^* (Или, что то же самое, часть подцелей удается сопоставить с утверждениями программы.- Прим. пер.)

Если проследить за работой программы в процессе определения возврата Джо с помощью первого правила отношения age, то можно увидеть причины, порождающие значительно большую неэффективность. Все в принципе хорошо до тех пор, пока не достигается условие (either ... or...). Процесс обработки запроса после достижения этого условия показан ниже:

(3 1): either branch

[снова попробовать (1 l)...]

Может показаться, что хороший механизм обработки запросов в данном случае приносит больше вреда, чем пользы. Ведь программа вынуждена оценивать каждое условие в конструкции (either... or...); причем все процессы сопоставления оканчиваются неудачей. После этого управление вновь передается первому утверждению в первом условии (1 1), т. е. делается попытка найти новое значение X, которое содержится в утверждении типа

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

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

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

1. Можно использовать два правила age1 и age2 вместо уже имеющихся и, кроме того, ввести новое третье правило, которое даст возможность выбрать либо agel, либо age2. Это третье правило будет иметь вид

X age Y if

(either X agel Y and/or X age2 Y).

В данном случае отношение "/" позволяет предотвратить использование age2, если использование age1 завершилось успешно.

2. Можно на основе двух правил отношения age сконструировать одно. Причем сделать это надо таким образом, чтобы кандидат на решение, удовлетворяющий двум первым условиям:

и

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

Перед тем как идти дальше, наверное, полезно проследить, как меняется содержимое стека в процессе обработки запроса (рис. 3.2 и 3.3). Изображенное на этих рисунках не следует интерпретировать как точную копию состояний памяти - скорее рисунки дают обобщенную картину выполняемых процессов. Центральный столбец на рис. 3.2 отражает структуру стека на разных этапах обработки запроса; левый столбец содержит составные номера утверждений, используемые и программой трассировки; и, наконец, правый столбец содержит информацию о последнем помещенном в стек элементе. Отметим, что, анализируя рисунки, необходимо учитывать существование специальных внутренних кодов, используемых для представления различных элементов* помещенных в стек.

Рис. 3.2. Процесс изменения состояния стека во время обработки запроса. Рис. 3.3. Изменение состояния стека в процессе реализации механизма возврата

Элементы попадают в стек именно в том порядке, в котором они обрабатываются программой; поэтому первым, помещенным в стек, элементом является

Это обозначает не что иное, как первое утверждение отношения born, которое в конце концов будет интерпретироваться как

Затем в стек будет помещен элемент now 1 - первое утверждение (оно одновременно и единственное) отношения now. После него - 5 LESS 9, затем символ "/", используемый для предотвращения возврата при поиске альтернативных вариантов, и, наконец, будет получено решение 35 = 1985 - 1950. Заключительное состояние стека перед возвратом изображено в нижней части рис. 3.2. Именно последний помещенный в стек элемент обеспечивает ответ на запрос, который будет выглядеть так:

На рис. 3.3 показано изменение состояний стека в результате операций, выполняемых в процессе возврата. Последний элемент, представляющий собой отношение SUM, выталкивается из стека и повторно не обрабатывается, поскольку альтернативных решений для него нет. Если бы альтернативное решение существовало, оно помешалось бы в стек и печаталось. Следующим выталкиваемым из стека элементом является условие (either ... or ...), но присутствие отношения "/" предотвращает на данном шаге выполнение возврата для поиска альтернативных вариантов. В конце концов из стека выталкивается born 1 и следом за этим в стек сразу же помещается born 2. Далее повторяется процесс, аналогичный изображенному на рис. 3.2, и так продолжается до тех пор, пока все утверждения, описывающие отношение born, не будут исчерпаны. В результате использования первого утверждения отношения age никаких новых решений, кроме

получено не будет. После этого аналогичная процедура повторяется для второго утверждения отношения age.

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

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

Ниже приведена более эффективная программа, позволяющая определить возраст по дате рождения и текущей дате:

Betty born (3 5 1950)

(either (either x LESS 9 and / or x leq 9 and Z leq 22 and /) and SUM (Y у 1985) and / or SUM (Y у 1984))

Возможность создания такой программы появилась только после изучения протокола трассировки первоначальной версии программы, выполняющей ту же самую функцию. Отметим главные преимущества последнего варианта программы. Во-первых, ояношение age определяется теперь с помощью только одного утверждения; во-вторых, следует определять текущую дату и, в-третьих, те люди, чьи дни рождения в текущем году еще не прошли, распознаются автоматически, поскольку данные о них не удовлетворяют первой части правила. Информацию о текущей дате можно включить в правило с помощью отношения update, использующего, в свою очередь, отношение is-told. Но если Вам необходимо провести трассировку, то лучше все же избежать хотя бы временно применения отношения update, что позволит сэкономить память. Ниже приводится часть протокола трассировки последней версии программы:

all-trace (x у: х age y)

[снова попробовать (1 1)]

Далее приводится текст отношения update, использование В которого позволяет пользователю вводить нужную ему дату:

update X if

(X1 x1 y))) add

Чтобы использовать отношение update, необходимо ввести

all (x: update x)

[определить все (х : модифицировать х)]

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

Анализ протокола трассировки позволяет заключить, что попытки осуществить возврат с целью поиска альтернативных решений в соответствии с конструкцией (either ... or ...) сразу игнорируются из-за присутствия отношения "/".