为什么这个动态版本的斐波那契程序比另一个快得难以置信?序言解决方案 [英] Why this dynamic version of Fibonacci program is incredibly faster then this other? Prolog solutions

问题描述

我正在使用SWI Prolog学习Prolog，对斐波那契数计算程序的以下两种解法有疑问:

I am learning Prolog using SWI Prolog and I have a doubt about the followings two solutions of the Fibonacci number calculation program:

第一个是这样的:

fib(1,1).   
fib(2,1).   


fib(N,F) :- N > 2,      
            N1 is N-1,      
        fib(N1,F1),     
            N2 is N-2,      
            fib(N2,F2),     
            F is F1+F2. 

我很清楚它的工作原理，非常简单.

It is pretty clear for me hw it work, it is very simple.

然后我有第二个版本，阅读代码，似乎和前一个版本一样工作，但之后它计算了 N 的斐波那契数，通过 asserta/2 将其保存在 Prolog 数据库中谓词之后重用它.

Then I have this second version that, reading the code, seems to work as the previous one but after that it have calculate the Fibonacci number of N save it in the Prolog database by asserta/2 predicate to reuse it after.

例如，如果我计算 10 和 11 的斐波那契数，当我要计算 12 的斐波那契数时，我会认为它使用前 2 次计算的结果.

So for example if I calculate the Fibonacci number for 10 and for 11 when I go to calculate the Fibonacci number for 12 I will aspect that it use the result of the previous 2 computations.

所以我的代码是:

:-dynamic fibDyn/2.

fibDyn(1,1).
fibDyn(2,1).

fibDyn(N,F) :- N > 2,
               N1 is N-1,
               fibDyn(N1,F1),
               N2 is N-2,
               fibDyn(N2,F2),
               F is F1+F2,
               asserta(fibDyn(N,F)).

在我看来，逻辑与上一个相同:

It seems to me that the logic is the same of the previous one:

如果 N>2，F 是 N 的斐波那契数，并使用递归计算 N 的斐波那契数(如前面的例子)

F is the Fibonacci number of N if N>2 and use the recursion for calculate the Fibonacci number of N (as in the preious example)

如果我要求计算一个我已经计算并放入其前辈(或其中一些)的斐波那契数数据库中的数字的斐波那契数，我希望程序更快，但在我看来它以一种奇怪的方式工作:它太快了，并且能够直接计算非常大的整数的斐波那契数(另一个版本在处理如此大的数字时出错)

I expect that the program is faster if I ask to calculate the number of a Fibonacci number for a number that I have already calculated and put into the database Fibonacci numbers of its predecessors (or some of them) but seems to me that it work in a strange way: it is too fast and is able to directly calculate the numbers of Fibonacci for very large integers (the other version goes wrong with such large numbers)

另一个奇怪的事情是，如果我对查询进行跟踪，我会得到这样的结果:

The other strange thing is that if I do a trace of a query I obtain something like this:

[trace]  ?- fibDyn(200,Fib).
   Call: (6) fibDyn(200, _G1158) ? creep
   Exit: (6) fibDyn(200, 280571172992510140037611932413038677189525) ? creep
Fib = 280571172992510140037611932413038677189525 .

如您所见，似乎不执行斐波那契谓词的代码而是直接获取结果(从哪里?！?！)

As you can see it seems that don't execute the code of the Fibonacci predicate but directly obtain the result (from where?!?!)

Instad 如果我执行这个查询(使用第一个版本)，我得到程序会计算它:

Instad if I execute this query (using the first version), I obtain that the program will calculate it:

[trace]  ?- fib(3,Fib).
   Call: (6) fib(3, _G1158) ? creep
^  Call: (7) 3>2 ? creep
^  Exit: (7) 3>2 ? creep
^  Call: (7) _G1233 is 3+ -1 ? creep
^  Exit: (7) 2 is 3+ -1 ? creep
   Call: (7) fib(2, _G1231) ? creep
   Exit: (7) fib(2, 1) ? creep
^  Call: (7) _G1236 is 3+ -2 ? creep
^  Exit: (7) 1 is 3+ -2 ? creep
   Call: (7) fib(1, _G1234) ? creep
   Exit: (7) fib(1, 1) ? creep
^  Call: (7) _G1158 is 1+1 ? creep
^  Exit: (7) 2 is 1+1 ? creep
   Exit: (6) fib(3, 2) ? creep
Fib = 2 .

为什么?我希望第二个版本(使用 asserta 谓词的版本)将计算两个数字的斐波那契数，并使用这些值生成下一个的解决方案.

Why? I would expect that the second version (the one that use asserta predicate) will calculate the Fibonacci number for two number and the it use these value for generate the solution of the following one.

例如，我可能有以下情况:我从未计算过任何斐波那契数，我要求计算 N=4 的斐波那契数，以便计算它(如在第二个发布的堆栈跟踪中).

For example I could have the following situation: I have never yet calculate any Fibonacci number and I ask for calculate the Fibonacci number of N=4 so it calculate it (as in the second posted stacktrace).

所以我要求计算 N=5 的斐波那契数，他使用保存的 N=4 斐波那契数.然后我要求它计算 N=6 的斐波那契数，它最终可以使用保存的 4 和 5 的斐波那契数

So I ask to calculate the Fibonacci number of N=5 and he use the Fibonacci of N=4 that it was saved. So then I ask it to calculate the Fibonacci number of N=6 and it finally could use the saved Fibonacci number of 4 and of 5

我错过了什么?你能帮我理解吗?

What am I missing? Can you help me to understand?

推荐答案

TL;DR:使用 retractall 从内存中删除所有先前断言的事实.

TL;DR: use retractall to erase all previously asserted facts from memory.

将您的定义更改为

:- dynamic fibDyn/2.
:- retractall( fibDyn(_,_) ).  %% without this, you'll retain all the previous 
                               %% facts even if you reload the program
fibDyn(1,1).
fibDyn(2,1).

fibDyn(N,F) :- N > 2,
               N1 is N-1,
               fibDyn(N1,F1),
               N2 is N-2,
               fibDyn(N2,F2),
               F is F1+F2,
               asserta( (fibDyn(N,F):-!) ).

注意断言规则内的切割.还要注意retractall 语句.没有它，即使您重新加载程序，所有先前断言的事实仍将保留在内存中.这就是可能是您立即获得结果的原因.

Notice the cut inside the asserted rule. Also notice the retractall statement. Without it, all the previously asserted facts will remain in memory even if you reload the program. That's probably the reason why you were getting your results immediately.

在你跑完之后?- fibDyn(10,X) 一次，就可以看到数据库中所有断言的事实:

After you've run e.g. ?- fibDyn(10,X) once, you can see all the asserted facts in the database:

12 ?- listing(fibDyn).
:- dynamic fibDyn/2.

fibDyn(10, 55) :- !.
fibDyn(9, 34) :- !.
fibDyn(8, 21) :- !.
fibDyn(7, 13) :- !.
fibDyn(6, 8) :- !.
fibDyn(5, 5) :- !.
fibDyn(4, 3) :- !.
fibDyn(3, 2) :- !.
fibDyn(1, 1).
fibDyn(2, 1).
fibDyn(A, D) :-
        A>2,
        B is A+ -1,
        fibDyn(B, E),
        C is A+ -2,
        fibDyn(C, F),
        D is E+F,
        asserta((fibDyn(A, D):-!)).

true.

这就是它运行如此之快的原因.您看到的速度差异是指数和线性时间复杂度算法之间的差异.

That is why it runs so fast. The difference in speed you're seeing is the difference between an exponential and linear time complexity algorithm.

下次调用它时，它可以访问所有先前计算的结果:

Next time you call it, it has access to all the previously calculated results:

[trace] 15 ?- fibDyn(10,X).
   Call: (6) fibDyn(10, _G1068) ? creep
   Exit: (6) fibDyn(10, 55) ? creep
X = 55.

[trace] 16 ?- 

这解释了您的 fibDyn(200,X) 调用跟踪输出.您可能在之前已经计算过一两次之后尝试过它.

This explains your fibDyn(200,X) call trace output. You've probably tried it after you've already calculated it once or twice before.

当我下次请求第 11 个号码时会发生以下情况:

Here's what happens when I next request the 11th number:

[trace] 35 ?- fibDyn(11,X).
   Call: (6) fibDyn(11, _G1068) ? creep
   Call: (7) 11>2 ? creep
   Exit: (7) 11>2 ? creep
   Call: (7) _G1143 is 11+ -1 ? creep
   Exit: (7) 10 is 11+ -1 ? creep
   Call: (7) fibDyn(10, _G1144) ? creep
   Exit: (7) fibDyn(10, 55) ? creep
   Call: (7) _G1146 is 11+ -2 ? creep
   Exit: (7) 9 is 11+ -2 ? creep
   Call: (7) fibDyn(9, _G1147) ? creep
   Exit: (7) fibDyn(9, 34) ? creep
   Call: (7) _G1068 is 55+34 ? creep
   Exit: (7) 89 is 55+34 ? creep
^  Call: (7) asserta((fibDyn(11, 89):-!)) ? creep
^  Exit: (7) asserta((fibDyn(11, 89):-!)) ? creep
   Exit: (6) fibDyn(11, 89) ? creep
X = 89.

[trace] 36 ?- 

又一次:

[trace] 36 ?- fibDyn(11,X).
   Call: (6) fibDyn(11, _G1068) ? creep
   Exit: (6) fibDyn(11, 89) ? creep
X = 89.

这篇关于为什么这个动态版本的斐波那契程序比另一个快得难以置信?序言解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！