在Prolog中排序大型列表:内存不足

Question

我正在尝试使用bubblesort对prolog中的10k元素列表进行排序,我得到了本地堆栈错误.Mergesort似乎是最好的选择,因为我没有得到相同输入的任何错误.但是我真的希望在输入数据很大的情况下获得一些运行时间,但我不能.有任何想法吗？

这是代码:

 %% NOTE: SWI-PROLOG USED

 %% generate_list(Limit, N, L): - insert upper limit and length of list N
 %% to get a random list with N numbers from 0 to limit
 generate_list(_, 0, []).
 generate_list(Limit, N, [Y|L]):-
    N =\= 0,
    random(0, Limit, Y),
    N1 is N-1,
    generate_list(Limit, N1, L).


 %% bubble(L, Ls, max):- insert list L and get max member of list by
 %% swapping members from the start of L.
 bubble([Z], [], Z).
 bubble([X,Y|L], [X|Ls], Z):- X =< Y, bubble([Y|L], Ls, Z).
 bubble([X,Y|L], [Y|Ls], Z):- X  > Y, bubble([X|L], Ls, Z).

 %% bubble_sort(List, Accumulator, Sorted_List)
 bubblesort([X], Ls, [X|Ls]).
 bubblesort(L, Accumulate, Result):- bubble(L, Ls, Max),
       bubblesort(Ls, [Max|Accumulate], Result).

 bubble_sort(L, Sorted):- bubblesort(L, [], Sorted).

你可以看到我正在使用尾递归.我还尝试使用以下方法扩大堆栈:

  set_prolog_stack(global, limit(100 000 000 000)).
  set_prolog_stack(trail,  limit(20 000 000 000)).
  set_prolog_stack(local,  limit(2 000 000 000)).

但它只运行了一段时间.最终我再次离开了本地堆栈.我应该使用其他语言,如C和malloc列表,还是不使用递归？

Answer 1

由于有两个答案,并且没有人明确指出你为什么会陷入"超出本地堆栈"的麻烦(Mat在你的问题的评论中说你的谓词不是确定性的,但没有解释确切原因).

您定义的两个谓词,即bubblesort/3和bubble/3,具有互斥条款.但Prolog(至少SWI-Prolog)不承认这些是相互排斥的.因此,创建选择点,您不会获得尾递归优化,并且可能没有垃圾收集(如果您想知道在何时何地发生,您需要使用您选择的实现进行测量).

你有两个不同的问题.

问题1:列出恰好一个元素

两个谓词中都会弹出此问题.在最简单的谓词可能:

foo([_]).
foo([_|T]) :-
    foo(T).

然后:

?- foo([a]).
true ;
false.

这并不奇怪; 考虑:

?- [a] = [a|[]].
true.

您可以使用一种称为滞后的技术来解决这个问题:

bar([H|T]) :-
    bar_1(T, H).
bar_1([], _).
bar_1([H|T], _) :-
    bar_1(T, H).

然后:

?- bar([a]).
true.

在定义中bar_1/2,第一个子句的第一个参数是空列表; 第二个子句的第一个参数是一个非空列表(一个至少包含一个元素和一个尾部的列表).当所有条款显然是独占的时,Prolog不会创建选择点.什么明显的手段将取决于实现,但通常情况下,当第一个参数的所有条款都具有不同的所有条款仿函数,然后创建别无选择点.

尝试以下(您可能会得到不同的结果,但消息是相同的):

?- functor([], Name, Arity).
Name = [],
Arity = 0.

?- functor([_|_], Name, Arity).
Name = '[|]',
Arity = 2.

通过Mat 查看此问题和答案,了解如何使用它来使您的程序具有确定性.

Mat,在他的回答中,如果我看得正确,就会使用这种方法.

问题2:条款正文中的约束(条件)

这是第二和第三个条款的问题bubble/3.在选择最少两个元素的教科书"正确"示例中:

min(A, B, B) :- B @< A.
min(A, B, A) :- A @=< B.

然后:

?- min(1,2,1).
true.

但:

?- min(2,1,1).
true ;
false.

你可以通过两种方式来解决这个问题:通过做Mat正在做的事情,即使用compare/3,确定性地成功; 或者,通过做CapelliC正在做的事情,即使用if-then-else.

垫:

min_m(A, B, Min) :-
    compare(Order, A, B),
    min_order(Order, A, B, Min).
min_order(<, A, _, A).
min_order(=, A, _, A).
min_order(>, _, B, B).

和卡罗:

min_c(A, B, Min) :-
    (   B @< A
    ->  Min = B
    ;   Min = A
    ).

我知道总会有至少和头脑一样多的意见,但两者都很好,取决于你在做什么.

PS

您可以使用内置length/2生成列表,并重写generate_list/3这样的:

generate_list(Limit, Len, List) :-
    length(List, Len),
    random_pos_ints(List, Limit).

random_pos_ints([], _).
random_pos_ints([H|T], Limit) :-
    random(0, Limit, H),
    random_pos_ints(T, Limit).

帮助程序random_pos_ints/2是一个简单的谓词,可以表达为maplist:

generate_list(Limit, Len, List) :-
    length(List, Len),
    maplist(random(0, Limit), List).    

Answer 2

bubble/3如果第一个参数被实例化,那么这个版本是确定性的,因此尾部调用优化(更具体地说,尾递归优化)适用:

bubble([L|Ls0], Ls, Max) :- phrase(bubble_(Ls0, L, Max), Ls).

bubble_([], Max, Max) --> [].
bubble_([L0|Ls0], Max0, Max) -->
        elements_max(L0, Max0, Max1),
        bubble_(Ls0, Max1, Max).

elements_max(X, Y, Max) -->
        { compare(C, X, Y) },
        c_max(C, X, Y, Max).

c_max(<, X, Y, Y) --> [X].
c_max(=, X, Y, Y) --> [X].
c_max(>, X, Y, X) --> [Y].

示例用法,程序的其余部分保持不变(运行时间取决于随机列表,如果要重现这些结果则不好 - 提示:引入随机种子作为参数来修复此问题):

?- generate_list(100, 10_000, Ls), time(bubble_sort(Ls, Ls1)).
% 200,099,991 inferences, 29.769 CPU in 34.471 seconds
...

要测试不同版本,请使用可用于可靠地重现相同初始列表的查询版本,例如:

?- numlist(1, 10_000, Ls0), time(bubble_sort(Ls0, Ls)).

好消息是:如果您只使用zcompare/3from library(clpfd)而不是compare/3,则获得可以在所有方向使用的版本:

?- bubble(Ls0, Ls, Max).
Ls0 = [Max],
Ls = [] ;
Ls0 = [Max, _G677],
Ls = [_G677],
_G677#=<Max+ -1,
zcompare(<, _G677, Max) ;
Ls0 = [Max, _G949, _G952],
Ls = [_G949, _G952],
_G952#=<Max+ -1,
_G949#=<Max+ -1,
zcompare(<, _G952, Max),
zcompare(<, _G949, Max) ;
etc.

这描述了整数之间的一般关系.