Повышение эффективности путем внесения в базу данных производных фактов

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

В качестве примера рассмотрим программу вычисления Я-то числа Фибоначчи для заданного N. Ряд Фибоначчи имеет следующий вид: 1, 1, 2, 3, ъ, S, 13,...

Каждое число в этом ряде, за исключением первых двух, представляет собой сумму предыдущих двух чисел. Определим предикат liib; в, F)

для вычисления N-ro числа Фибоначчи, F, соответствующего заданному значению N. Эти числа можно получить последовательно, начиная с К = 1. В приведенной ниже программе fib вначале рассматриваются первые два числа Фибоначчи как два част­ных случая, а затем задается общее правило, касающееся ряда Фибоначчи.

fib E 1,1). % 1-е число Фибоначчи

fib(2, 1). % 2-е число Фибоначчи

fib(И, F):- % Ы-е числе Фибоначчи, N > 2

N > 2,

Ml is N - 1, Eifo(Ml, Fl!,

82 is N - 2, fib (N2, F2),

" is Fl + F2. % Ы-с числе - сумма дзух предшествующи к ему чисел

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

?- fib(6, F).

186 Часть I. Язык Prolog

На рис. 8.2 иллюстрируются характерные особенности вычислительного процесса. Например, третье число Фибоначчи, f (3), требуется в трех местах, и каждый раз повторяется одно и то же вычисление.

 

1 1

Рис. R.2. Вычисление 6-го числа Фибоначчи с помощью процедуры fib

Этого можно легко избежать, запоминая каждое вновь полученное число Фибо­наччи. Идея состоит в том, что следует использовать встроенную процедуру asserta и вводить в базу данных такие (промежуточные) результаты как факты. Эти факты должны предшествовать другим предложениям, касающимся fib, чтобы можно было исключить необходимость в использовании общего правила в тех случаях, если ре­зультат уже известен. Модифицированная процедура fib2 отличается от процедуры fib только тем, что в ней предусмотрено внесение информации в базу данных сле­дующим образом:

fib2! 1,1}. % 1-е число Фибоначчи

fib2(2, 1). % 2-е число Фибоначчи

fib2( N, F) :- % Н-е ЧИ С Л О Фибоначчи, Ы> 2

N > 2,

N1 is N - 1,

fib2(Ml, Fib

N2 is К - 2,

fib2(N2, F2),

1-е число

F is Fl + F2,

asserta [ fxb2 [ H,

:-■:

К Запомнить

Эта программа предпринимает попытки найти ответ на любую цель fib2, вначале рассматривая сохраненные в базе данных факты, касающиеся этого отношения, и только после этого обращается к общему правилу. В результате после выполнения цели fib2 { N, Fi все числа Фибоначчи вплоть до N-го числа становятся зафиксиро-

Плава 8. Стиль и методы программирования

 

ванными. На рис, 8.3 показан процесс вычисления 6-го числа Фибоначчи процедурой fib2. Сравнение с рис. 8.2 показывает, что вычислительная сложность процедуры уменьшилась. Чем больше значение К, тем более существенным становится это уменьшение.

3(из базы данных)

 

Рис. 8.3. Вычисление 6-ю числа Фибоначчи с помощью процедуры £1Ь2, которая запоминает предыдущие результаты; благодаря, этому сокращается объем вы­числений, по сравнению с процедурой fib (см. рис. 8.2)

Внесение в базу данных промежуточных результатов, называемое также кэширо­ванием, — это стандартный метод предотвращения повторных вычислений. Но сле­дует отметить, что в случае чисел Фибоначчи можно применить более предпочти­тельный метод предотвращения повторных вычислений с использованием другого ал­горитма, а не вносить а базу данных промежуточные результаты. Этот другой алгоритм приводит к созданию программы, которая является более трудной для по­нимания, но более эффективной при выполнении. В предыдущей версии М-е число Фибоначчи определялось как сумма своих двух предшественников, а для разверты­вания всего процесса вычислений "в направлении вниз", к двум первоначальным числам Фибоначчи применялись рекурсивные вызовы. Вместо этого можно организо­вать работу "в направлении вверх", начиная с двух исходных чисел и вычисляя зна­чения ряда одно за другим, по возрастанию. При этом достаточно только во время остановиться после получения Ы-го значения. Основная часть работы в такой про­грамме выполняется с помощью следующей процедуры: forwardfib(К, N, Fl, F2, F)

где F1 и F2 — Ш-1)-еи М-е числа Фибоначчи, a F - Ы-е число Фибоначчи. Принцип действия отношения forwardfхЬпоказан на рис, 8.4. В соответствии с этим рисун­ком процедура forwardfib находит последовательность преобразований, позволяю-

Часть I. Язык Prolog

щую достичь окончательной конфигурации (при которой М = N) из заданной началь­ной конфигурации. При вызове forwardfib все параметры, кроме F, должны быть конкретизированными, а К должно быть меньше или равно N. Соответствующая про­грамма показана ниже.

% Первые двачисла Фибоначчи равны 1 "? Н-е число Фибоначчи достигнуто % N-e число Фибоначчи еще не достигнуто

Eib3! я, F):-

forwardfib(2, N, 1, 1, F). forwardfib! M, N, П., F2, F2}:-

М ?- N. forwardfib! И, N, F1, Г2, F):-

!•: <::,

HextM is И + 1,

HeJStF2 is Fl + F2,

forwardfib(NextM, И, F2, NextF2, F).

 

 

Начальная конфигурация. гдаМ = 2

Перевод

от конфигурации М

кМ+ 1

Конечная конфигурация. где М = N

Рис. 8.4. Соотношения между числами ряда Фибоначчи; конфигурация, обозна­ченная большим кружком, определяется тремя компонентами: индексом и и двумя последовательными числами Фибоначчи. f(M-l) и £<М)

Следует отметить, что в процедуре forwardfib применяется хвостовая рекурсия, а м, F1 и F2 представляют собой накапливающие параметры.