为什么这个动态版本的斐波那契数列程序比另一个要快得多?Prolog的解决方案

Question

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

第一个是:

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. 

我很清楚它是如何工作的，它很简单。

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

因此，例如，如果我计算10和11的斐波那契数，当我去计算12的斐波那契数时，我将使用前两次计算的结果。

所以我的代码是:

:-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)).

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

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

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

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

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

正如你所看到的，似乎不执行斐波那契谓词的代码，而是直接获得结果(从哪里?!?!)

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

[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 .

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

例如，我可以有以下情况:我从来没有计算过任何斐波那契数，我要求计算N=4的斐波那契数，所以它计算它(如第二个张贴的stacktrace)。

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

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

Answer 1

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

将定义更改为

:- 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语句。如果没有它，即使重新加载程序，所有先前断言的事实也将保留在内存中。这可能就是为什么你能立即得到结果的原因。

当你运行例如?- fibDyn(10,X)一次后，你可以看到数据库中所有断言的事实:

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.

这就是为什么它跑得这么快。你看到的速度差异是指数和线性时间复杂度算法之间的差异。

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

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

这解释了您的fibDyn(200,X)调用跟踪输出。你可能在计算过一两次之后就尝试过了。

下面是当我再次请求第11个数字时发生的情况:

[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.

您的第一个解决方案

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
  . 

不是很有效。对于初学者来说，它不是尾部递归的，它以指数时间运行(如前所述)。我敢打赌，这个应该在线性时间内运行的递归实现至少会和您的动态解决方案一样快(如果不是更快的话):

fibonacci( 1 , 1 ) .
fibonacci( 2 , 1 ) .
fibonacci( N , V ) :- N>2, fibonacci( 1 , 1 , 3 , N , V ) .
fibonacci( X , Y , N , N , V ) :-
  V is X+Y
  .
fibonacci( X , Y , T , N , V ) :-
  Z  is X + Y ,
  T1 is T + 1 ,
  fibonacci( Y , Z , T1 , N , V )
  .

需要注意的重要事项是斐波那契序列只需要跟踪序列中的前两个元素。为什么每次迭代都要重新计算它们呢?就像上面那样保持滑动窗口。

斐波那契数列的一个更有趣的性质是，当你进一步向序列中移动时，任何两个相邻值的比率越来越接近phi，即黄金平均数。更有趣的是，无论使用哪两个值作为种子序列，只要它们是非负的，并且至少有一个为零，这都成立。

一个更通用的解决方案，可以让你用任何你想要的值来播种序列，可能是这样的:

fibonacci( Seed1 , Seed2 , Limit , N , Value ) :-
  Seed1 >= 0       ,
  Seed2 >= 0       ,
  X is Seed1+Seed2 ,
  X > 0            ,
  Limit >= 0        ,
  fibonacci( Seed1 , Seed2 , 3 , Limit , N , Value )
  .
fibonacci( S1 , _  , _ , L , 1 , S1 ) :- 1 =< L .
fibonacci( _  , S2 , _ , L , 2 , S2 ) :- 2 =< L .
fibonacci( S1 , S2 , T , L , T , V  ) :-          % T > 2,
  T =< L ,
  V is S1+S2
  .
fibonacci( S1 , S2 , T , L , N , V ) :- N > T,    % T > 2,
  T =< L        ,
  S3 is S1 + S2 ,
  T1 is T  + 1  ,
  fibonnaci( S2 , S3 , T1 , L , N , V )
  .

这不是关于Prolog的，而是关于算法的。朴素的递归解决方案需要O(2**n)步来计算，而第二个版本使用记忆法将其减少到O(n)步。

要了解这是什么意思，请尝试在纸上计算fib(4)，而不要查找之前计算过的内容。然后，再做一遍，但要做好笔记，尽可能地查阅资料。

之后，如果您尝试以第一种方式计算fib(5)，则必须首先计算fib(4)和fib(3)。这就是你的第一个算法。注意，为了计算fib(4)，你需要再次计算fib(3)。所以你最终会一遍又一遍地做同样的计算。

另一方面，您可以查找这两个值并立即得到结果。这就是第二个算法的作用。

对于O(2**n)，您需要为每个后续值做两倍的工作，而对于O(n)，您只需要做与前一个值相同的工作。