3

我在 GNU Prolog 中有这段代码，但我不知道为什么 50 元素配对列表很慢：

pairwise_min( [X], X ) :- !.
pairwise_min( [(A,B)|T], (A,B) ) :-
    pairwise_min( T, (_,B1) ),
    B1 > B,
    !.
pairwise_min( [(_,B)|T], (A1,B1) ) :-
    pairwise_min( T, (A1,B1) ),
    B1 =< B,
    !.

以下查询需要 10 秒：

?- pairwise_min( [(25,25),(24,24),(23,23),(22,22),(21,21),(20,20),(19,19),(18,18),(17,17),(16,16),(15,15),(14,14),(13,13),(12,12),(11,11),(10,10),(9,9),(8,8),(7,7),(6,6),(5,5),(4,4),(3,3),(2,2),(1,1)], X ).

我能做些什么来快速找到这个最小值？

4

3 回答 3

4

跟踪时可以快速看到问题：

?- trace, pairwise_min( [(25,25),(24,24),(23,23),(22,22),(21,21),(20,20),(19,19),(18,18),(17,17),(16,16),(15,15),(14,14),(13,13),(12,12),(11,11),(10,10),(9,9),(8,8),(7,7),(6,6),(5,5),(4,4),(3,3),(2,2),(1,1)], X ).
   Call: (7) pairwise_min([ (25, 25), (24, 24), (23, 23), (22, 22), (21, 21), (20, 20), (19, 19), (..., ...)|...], _G737) ? 
   ... snip ...
   Call: (30) pairwise_min([ (2, 2), (1, 1)], (_G1065, _G1066)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1068, _G1069)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1>2 ? 
   Fail: (31) 1>2 ? 
   Redo: (30) pairwise_min([ (2, 2), (1, 1)], (_G1065, _G1066)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1065, _G1066)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1=<2 ? 
   Exit: (31) 1=<2 ? 
   Exit: (30) pairwise_min([ (2, 2), (1, 1)], (1, 1)) ? 
   Call: (30) 1>3 ? 
   Fail: (30) 1>3 ? 
   Redo: (29) pairwise_min([ (3, 3), (2, 2), (1, 1)], (_G1062, _G1063)) ? 
   Call: (30) pairwise_min([ (2, 2), (1, 1)], (_G1062, _G1063)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1068, _G1069)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1>2 ? 
   Fail: (31) 1>2 ? 
   Redo: (30) pairwise_min([ (2, 2), (1, 1)], (_G1062, _G1063)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1062, _G1063)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1=<2 ? 
   Exit: (31) 1=<2 ?

pairwise_min(T, ...)基本上，问题是你在这两种情况下都会打电话，即使在第二种情况下它不会有所不同。尾部的成对最小值是尾部的成对最小值，无论当前元素如何检查它。

一个好的解决方案是通过使用显式条件来消除第二条规则，如下所示：

pairwise_min( [X], X ) :- !.
pairwise_min( [(A,B)|T], (RA,RB) ) :-
    pairwise_min(T, (A1,B1)), !,
    (B1 > B -> (RA = A,  RB = B)
             ; (RA = A1, RB = B1)).

对我来说，可读性的一个重大障碍是，我并没有真正理解你试图用你的成对最小值实现什么样的排序。但无论如何，将来将其提取到自己的谓词中将是一个好主意。我对你的最低要求没有信心；不是真的@</2会做你想做的事吗？如果是这种情况，您可以使用非常紧凑的尾递归折叠来做到这一点：

minimum([X|Xs], Min) :- minimum(Xs, X, Min).
minimum([], Min, Min).
minimum([X|Xs], MinSoFar, Min) :-
    (X @< MinSoFar -> minimum(Xs,        X, Min)
                    ; minimum(Xs, MinSoFar, Min)).

如果不是这种情况，您可以编写自己的谓词min_pair/2来比较两对，并使用它来代替@</2并获得好处。或者从pairwise_min/2上面的修改中调用它，看看尾调用优化的好处。

我认为您在改进此版本的性能方面会遇到一些麻烦。

于 2013-12-04T23:47:03.570 回答
3

从某种意义上说，您很幸运能找到正确的查询。想象一下，你会选择一个升序列表。在这种情况下，您暂时会体验到更快的程序。但在演示日，降序排列会毁了你的节目。

要了解实际发生的情况，只查看程序的非常小的片段通常非常有用。而且由于您的削减本质上是绿色削减，我们可能会这样做，即使他们在场。我会将false目标添加到您的计划中。不要指望这个片段有任何意义。它已经没有了。但是，它向我们展示了 Prolog 必须探索的搜索空间：

pairwise_min（[X]，X）：-假，！.
pairwise_min( [(A,B)|T], (A,B) ) :-
    pairwise_min( T, (_,B1) ),假
    B1 > B ,
     ! .
pairwise_min( [(_,B)|T], (A1,B1) ) :-
    pairwise_min( T, (A1,B1) ),假
    B1 =< B ,
     ! .

结果现在独立于具体值（假设第二个参数未实例化）。现在，列表的每个元素都有两个选择。对于长度为 n 的列表，我们有 2 n 个选择。这就是产生这种开销的原因。要删除它，您必须更改可见部分中的某些内容。理想情况下，您在递归之前添加一些比较。

于 2014-06-12T20:45:09.760 回答
2

一个非常简单的定义，没有优化但相当快

pairwise_min(L, (A,B)) :-
    select((A,B), L, R),
    \+ ( member((A1,B1), R), B1 < B ).

无论如何，研究代码的性能将是理解 Prolog 执行模型的一个很好的方法

于 2013-12-05T00:24:34.657 回答