Чтобы продолжить работу с 2), вам придется прочитать вводную работу для Пролога, например Learn Prolog Now .
Но давайте ответим на вопрос о вычислении ряда Фибоначчи с помощью программы Prolog (которая является своего рода «программой logi c», но на самом деле просто вычисляет вперед), которая обменивает память на циклы ЦП
Запись в Википедии о Dynami c Программирование фактически содержит секцию о Последовательности Фибоначчи .
Как правильно сказано, проблема вычисления последовательности состоит из двух Особенности:
- Рекурсивный
- «Перекрывающиеся подзадачи»
Второй означает, что нас попросят пересчитать то же самое f (х) снова и снова. Таким образом, мы находимся в ситуации, когда мы можем обменять это повторяющееся усилие на пространство (то есть на память), а именно путем кэширования результатов вычисления f (x) . f должна быть реальной функцией: одни и те же аргументы всегда дают одинаковые результаты. Никаких запросов пользователю или чему-либо еще!
Использование "табуляции"
На самом деле, многие процессоры (движки) Prolog уже имеют встроенную возможность для включения кэширования для определенных предикатов: он называется Включение или «Мемоизация» и его обобщение на удивление сложны. Здесь - это страница из SWI-Prolog (я использую SWI-Prolog, потому что это тот, который я обычно использую, но XSB Prolog и B-Prolog могут иметь более полные реализации, не зная, в каком состоянии сейчас находится ).
Непосредственно из пролога SWI выполните c, мы получим эту реализацию. Обратите внимание на директиву :- table fib/2 , которая включает кэширование результатов для fib/2:
:- table fib_tabled/2.
fib_tabled(0, 1) :- !.
fib_tabled(1, 1) :- !.
fib_tabled(N, F) :-
N > 1,
N1 is N-1,
N2 is N-2,
fib_tabled(N1, F1),
fib_tabled(N2, F2),
F is F1+F2.
Выполнение вышеуказанного эффективно!
Включение включено:
?- time(fib_tabled(1000,F)).
% 4 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 197141 Lips)
F = 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501.
Включение отключено:
?- time(fib_tabled(1000,F)).
...uh forget it.
Обратите внимание, что fib/2 ведет себя как функция больше, чем предикат . Режим аннотации будет fib(+N,-F): N входит, F выходит! В SWI Prolog произвольные длинные числа поступают через GNU Multiple Precision Arithmeti c Library
Не используется табулирование
Но мы хотим найти решение, не полагаясь на табулирование ,
Не глядя на эту страницу вообще ...
У нас есть два способа сделать это:
- Сверху вниз : Начиная вычисление fib (N) при N и рекурсивное разложение до достижения fib (0) и fib (1) . Здесь мы должны отложить вычисление более высоких значений до тех пор, пока более низкие значения не станут известны. Это звучит как «Dynami c Programming» и то, что мы хотим сделать.
- Вверх : Начинается вычисление fib (N) в 0 и 1 (для которых известны результаты) и итеративно движется вверх до N . Здесь мы знаем все нижние значения fib (m) , 0 <= m <n, при любом <em>n , при этом двигаясь в направлении N . Эффективно, но не то, что мы хотим сделать. (код для этого также находится внизу этой страницы ).
Итак ... "сверху вниз" это так.
Подходы сверху вниз
Нам нужен кеш, в котором хранятся уже вычисленные результаты.
Подход 1
В Прологе нет «изменяемых структур данных» (в принципе), поэтому первый подход будет следующим: с учетом существующего кэша нам придется построить новый кеш из него, вставка недавно вычисленного значения и продолжение работы с этим новым кешем. Кеш становится «горячим картофелем», который передается от одного звонка к другому. Или это «пронизывает» вычисления. Он появляется в двух местах в каждом списке аргументов: входящий, выходящий.
% In goes: N and CacheIn,
% Out comes: X and CacheOut
% as indicated by the (purely notational in bare Prolog) "mode flags"
% fib(+N, -X, +CacheIn, -CacheOut)
fib(N, X, CacheIn, CacheOut) :- ....
Обратите внимание, что кеш - это нечто, находящееся "вне проблемы": оно должно быть актуальным и доступным для всех вызовов fib в любое время в самом свежем виде версия. В императивном языке программирования это будет изменчивая структура, на которую ссылаются fib . Способ Prolog на самом деле также гарантирует, что каждый вызов fib имеет доступ к последнему кешу. (докажи это!).
(Но что, если мы действительно будем иметь дело с ... параллелизмом (в отличие от простого параллелизма)? Тогда проблемы становятся более масштабными, и необходима синхронизация при доступе к кешу. Мы не go Значительные усилия по детализированному параллелизму в Прологе были заброшены )
Итак, кеш может быть списком длины N + 1 , где мы храним значение fib (n) в индексе n (список индексов go из 0), если оно известно. Если это не известно, мы можем, например, сохранить там 0.
Альтернативный подход может быть основан на кеше, построенном на карте . Они доступны в SWI-Prolog напрямую как " dicts " и, конечно, в других прологах через библиотеки, но с другим синтаксисом (Dict еще не стандартизирован.).
Подход 2
Но тогда есть гораздо лучший подход . Вместо вставки 0 для неизвестного пока в кеш, мы можем вставить fre sh, неограниченные переменные. Переменная - это глобальные данные, которые являются версионными (повышенная версия в точках выбора, пониженная версия при обратном отслеживании), и ее можно сделать «более точной» или «уточненной» по мере того, как время прогрессирует, например, установить в целое число (и все, вы не можете "неточный").
После некоторых проб и ошибок мы находим решение, которое просто принимает Cache (а не CacheIn и CacheOut) и уточняет переменная fre sh в кеше в позиции от x до fib (x) . Это очень близко к обязательному подходу - иметь глобальный кеш, значения которого устанавливаются в ходе вычислений. Ключом является предикат var(X), который фактически проверяет, является ли X неопределенной переменной или чем-то еще (в данном случае, действительным целочисленным значением).
Подход 3
(Это вызывает еще одну идею, основанную не на видимом кеше, а на невидимом, управляемом Prolog на основе сопрограммирования и предиката freeze. Возможно, позже.)
В rosettacode.org , в разделе Фибоначчи / Пролог, дано довольно интересное решение. Он использует ленивые списки:
fib([0,1|X]) :-
ffib(0,1,X).
ffib(A,B,X) :-
freeze(X, (C is A+B, X=[C|Y], ffib(B,C,Y)) ).
?- fib(X), length(A,15), append(A,_,X), writeln(A).
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]
X = [0, 1, 1, 2, 3, 5, 8, 13, 21|...],
A = [0, 1, 1, 2, 3, 5, 8, 13, 21|...],
freeze(_16710, (_16840 is 233+377, _16710=[_16840|_16866], ffib(377, _16840, _16866))).
Это для дневного курса от Intro до Prolog. Позже.
Подход 2: Кэшировать как список переменных fre sh, глобально обновленных
Код
Хорошо, давайте начнем эту вечеринку.
Не думаю, что я нашел это с первой попытки. Если вы понимаете это, вы понимаете Пролог.
% The predicates visible to the user
fib_cached(0, 1) :- !.
fib_cached(1, 1) :- !.
fib_cached(N, X) :-
N>1,!, % useless guard and cut but good for documentation
Np is N+1,
length(Cache,Np), % create a cache as a list of Np fresh variables
nth0(0,Cache,1), % looks like a "get", actually a "set": Cache[0] := 1
nth0(1,Cache,1), % looks like a "get", actually a "set": Cache[1] := 1
nth0(N,Cache,X), % just the "pick the value" out of Cache and unify it with the result; in essence this is a communnication channel
fib_cached_sub(N, Cache). % fib_cached_sub doesn't even need to tells us the value, we will just look at the cache
% At this point, one could print: format("Cache is now: ~w\n",[Cache]).
% Under-the-surface predicate!
fib_cached_sub(N, Cache) :-
nth0(N,Cache,Q), % Unify Cache[N] with Q (Q is fresh, so this is a question)
var(Q), % Q is still a fresh variable!
!, % Commit to "we need to compute"
N1 is N-1,
N2 is N-2,
% Recursive calls! Calls don't indicate the result,
% they refine the cache! Note we will have a cache hit for N1=0,1
fib_cached_sub(N1, Cache),
fib_cached_sub(N2, Cache),
% On return, get values from the cache
nth0(N1,Cache,F1),
nth0(N2,Cache,F2),
F is F1+F2,
% A really interesting question is:
% Could cache contain an entry for fib(N) now?
% If not, why not? :-)
% Unify Cache[N] with F (F is a value, so this is a "assignment/refinment")
nth0(N,Cache,F).
% Default case of a cache hit. There is nothing to do.
fib_cached_sub(N, Cache) :-
nth0(N,Cache,Q),
\+var(Q).
Но это быстро?
Это эффективно по времени? Не так много, как табличный предикат:
?- time(fib_cached(1000,F)).
% 1,009,009 inferences, 0.114 CPU in 0.115 seconds (99% CPU, 8854526 Lips)
F = 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501.
Тесты
Время для тестирования с использованием средств тестирования SWI-Prolog
:-begin_tests(fibonacci).
test(fib_compare) :-
foreach(
between(0,100,N), fib_compare_results(N)).
fib_compare_results(N) :-
fib_tabled(N,Ft),
format("fib_tabled(~w) = ~w, ",[N,Ft]),
fib_cached(N,Fc),
format("fib_cached(~w) = ~w\n",[N,Fc]),
%format("N = ~d, F_tabled = ~d, F_cached = ~d\n",[N,Ft,Fc]),
Ft=:=Fc.
:-end_tests(fibonacci).
Запуск этого :
?- run_tests(fibonacci).
% PL-Unit: fibonacci fib_tabled(0) = 1, fib_cached(0) = 1
fib_tabled(1) = 1, fib_cached(1) = 1
fib_tabled(2) = 2, fib_cached(2) = 2
....
fib_tabled(100) = 573147844013817084101, fib_cached(100) = 573147844013817084101
. done
% test passed
true.
Подход 1. Кэширование в виде списка значений, локально обновляемых, «поточных»
Код
% The predicates visible to the user
fib_cachemutator(0, 1) :- !.
fib_cachemutator(1, 1) :- !.
fib_cachemutator(N, X) :-
N>1,!, % useless guard and cut but good for documentation
Nm is N-1,
findall(0,between(0,Nm,_),Ctmp), % create a cache as a list of N-1 0s
Cache = [1,1|Ctmp], % first two entries of cache are 1
fib_cachemutator_sub(N, Cache, CacheOut), % Cache goes in, different Cache comes out
nth0(N,CacheOut,X).
% The under-the-surface predicates
% Cache miss
fib_cachemutator_sub(N, Cache, CacheOut) :-
nth0(N,Cache,0), % there is still a 0 there
!, % commit to "we need to compute"
N1 is N-1,
N2 is N-2,
fib_cachemutator_sub(N1, Cache, CacheTmp),
fib_cachemutator_sub(N2, CacheTmp, CacheTmp2),
nth0(N1,CacheTmp2,F1),
nth0(N2,CacheTmp2,F2),
F is F1+F2,
update_cache(N,F,CacheTmp2,CacheOut).
% Cache hit
fib_cachemutator_sub(N, Cache, Cache) :-
nth0(N,Cache,F),
F > 0.
% Create a new cache ("Update the cache"). This is laborious.
% I want an equivalent of
% https://perldoc.perl.org/functions/splice.html
update_cache(N,V,CacheIn,CacheOut) :-
split_list(CacheIn,N,_,Front,Back),
append([Front, [V], Back], CacheOut).
% Split a list at position N (0-based):
% split_list(+List, +Index, Element, FrontOfListUpToIndex, BackOfListFromIndex)
split_list([L|Lr],N, El, [L|Front], Back) :-
N>0,!,
Nm is N-1,
split_list(Lr,Nm,El,Front,Back).
split_list([L|Lr],0, L, [], Lr).
Но это быстро?
Это эффективно по времени? Не так сильно, как табличный предикат:
?- time(fib_cachemutator(1000,F)).
% 2,860,996 inferences, 0.361 CPU in 0.363 seconds (99% CPU, 7930777 Lips)
F = 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501.
Тесты
Как обычно:
:-begin_tests(fibonacci_bis).
test(fib_compare) :-
foreach(
between(0,100,N), fib_compare_results(N)).
fib_compare_results(N) :-
fib_tabled(N,Ft),
format("fib_tabled(~w) = ~w, ",[N,Ft]),
fib_cachemutator(N,Fc),
format("fib_cachemutator(~w) = ~w\n",[N,Fc]),
%format("N = ~d, F_tabled = ~d, F_cached = ~d\n",[N,Ft,Fc]),
Ft=:=Fc.
:-end_tests(fibonacci_bis).
Запуск этого:
?- run_tests(fibonacci_bis).
% PL-Unit: fibonacci_bis fib_tabled(0) = 1, fib_cachemutator(0) = 1
fib_tabled(1) = 1, fib_cachemutator(1) = 1
fib_tabled(2) = 2, fib_cachemutator(2) = 2
fib_tabled(3) = 3, fib_cachemutator(3) = 3
fib_tabled(4) = 5, fib_cachemutator(4) = 5
....
fib_tabled(100) = 573147844013817084101, fib_cachemutator(100) = 573147844013817084101
. done
% test passed
true.