在 Prolog 中对大型列表进行排序：内存不足
Sorting large lists in Prolog: Not enough memory
我正在尝试使用 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 列表还是不使用递归？
免责声明：遵循@mat 的提示可能会更有收获...
我玩过你的代码，在我的实验中，本地堆栈溢出被抛出，列表长度接近 2500。然后我放置了一些剪切：
%% 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], [R|Ls], Z):-
( X =< Y -> (R,T)=(X,Y) ; (R,T)=(Y,X) ),
bubble([T|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).
然后我得到
?- time(generate_list(100,10000,L)),time(bubble_sort(L,S)).
% 60,000 inferences, 0.037 CPU in 0.037 seconds (99% CPU, 1618231 Lips)
% 174,710,407 inferences, 85.707 CPU in 86.016 seconds (100% CPU, 2038460 Lips)
L = [98, 19, 80, 24, 16, 59, 70, 39, 22|...],
S = [0, 0, 0, 0, 0, 0, 0, 0, 0|...]
.
所以，它正在工作，但非常缓慢，显示出二次复杂性...
这是 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)).
好处是：如果你只使用 library(clpfd) 中的 zcompare/3 而不是 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.
这描述了整数之间的一般关系。
因为有两个答案，而且没有人足够明确地指出你陷入 "out of local stack" 麻烦的原因（Mat 在对你的问题的评论中说你的谓词不是确定性的，但没有解释确切原因）。
您定义的两个谓词，即 bubblesort/3 和 bubble/3，具有互斥子句。但是 Prolog（至少 SWI-Prolog）不承认这些是互斥的。所以，创建了选择点，你没有得到尾递归优化，并且可能没有垃圾 collection（如果你想知道有多少去哪里和什么时候，你需要使用你选择的实现来衡量）。
你有两个不同的问题。
问题 1：只有一个元素的列表
这个问题在两个谓词中都会出现。在最简单的谓词中：
foo([_]).
foo([_|T]) :-
foo(T).
然后：
?- foo([a]).
true ;
false.
这并不奇怪；考虑：
?- [a] = [a|[]].
true.
您可以使用一种叫做 lagging:
的技术来解决这个问题
bar([H|T]) :-
bar_1(T, H).
bar_1([], _).
bar_1([H|T], _) :-
bar_1(T, H).
然后：
?- bar([a]).
true.
在bar_1/2的定义中，第一个子句的第一个参数是空列表；第二个子句的第一个参数是一个 non-empty 列表（一个至少有一个元素和尾巴的列表）。当所有子句 显然 排他时，Prolog 不会创建选择点。 obvious 的含义取决于实现，但通常，当所有子句的第一个参数都是具有不同 functors 的术语时，则没有选择点已创建。
尝试以下操作（您可能会得到不同的结果，但消息是一样的）：
?- functor([], Name, Arity).
Name = [],
Arity = 0.
?- functor([_|_], Name, Arity).
Name = '[|]',
Arity = 2.
请参阅 this question 和 Mat 的回答，了解如何使用它来使程序具有确定性。
如果我没看错的话，Mat 在他的回答中使用了这种方法。
问题 2：子句正文中的约束（条件）
这是bubble/3的第二个和第三个子句的问题。课本中"correct"选择两个元素中最小值的例子：
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 生成列表，并且 re-write 您的 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).
我正在尝试使用 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 列表还是不使用递归？
免责声明：遵循@mat 的提示可能会更有收获...
我玩过你的代码，在我的实验中，本地堆栈溢出被抛出，列表长度接近 2500。然后我放置了一些剪切：
%% 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], [R|Ls], Z):-
( X =< Y -> (R,T)=(X,Y) ; (R,T)=(Y,X) ),
bubble([T|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).
然后我得到
?- time(generate_list(100,10000,L)),time(bubble_sort(L,S)).
% 60,000 inferences, 0.037 CPU in 0.037 seconds (99% CPU, 1618231 Lips)
% 174,710,407 inferences, 85.707 CPU in 86.016 seconds (100% CPU, 2038460 Lips)
L = [98, 19, 80, 24, 16, 59, 70, 39, 22|...],
S = [0, 0, 0, 0, 0, 0, 0, 0, 0|...]
.
所以，它正在工作，但非常缓慢，显示出二次复杂性...
这是 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)).
好处是：如果你只使用 library(clpfd) 中的 zcompare/3 而不是 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.
这描述了整数之间的一般关系。
因为有两个答案，而且没有人足够明确地指出你陷入 "out of local stack" 麻烦的原因（Mat 在对你的问题的评论中说你的谓词不是确定性的，但没有解释确切原因）。
您定义的两个谓词，即 bubblesort/3 和 bubble/3，具有互斥子句。但是 Prolog（至少 SWI-Prolog）不承认这些是互斥的。所以，创建了选择点，你没有得到尾递归优化，并且可能没有垃圾 collection（如果你想知道有多少去哪里和什么时候，你需要使用你选择的实现来衡量）。
你有两个不同的问题。
问题 1：只有一个元素的列表
这个问题在两个谓词中都会出现。在最简单的谓词中：
foo([_]).
foo([_|T]) :-
foo(T).
然后：
?- foo([a]).
true ;
false.
这并不奇怪；考虑：
?- [a] = [a|[]].
true.
您可以使用一种叫做 lagging:
的技术来解决这个问题bar([H|T]) :-
bar_1(T, H).
bar_1([], _).
bar_1([H|T], _) :-
bar_1(T, H).
然后：
?- bar([a]).
true.
在bar_1/2的定义中，第一个子句的第一个参数是空列表；第二个子句的第一个参数是一个 non-empty 列表（一个至少有一个元素和尾巴的列表）。当所有子句 显然 排他时，Prolog 不会创建选择点。 obvious 的含义取决于实现，但通常，当所有子句的第一个参数都是具有不同 functors 的术语时，则没有选择点已创建。
尝试以下操作（您可能会得到不同的结果，但消息是一样的）：
?- functor([], Name, Arity).
Name = [],
Arity = 0.
?- functor([_|_], Name, Arity).
Name = '[|]',
Arity = 2.
请参阅 this question 和 Mat 的回答，了解如何使用它来使程序具有确定性。
如果我没看错的话，Mat 在他的回答中使用了这种方法。
问题 2：子句正文中的约束（条件）
这是bubble/3的第二个和第三个子句的问题。课本中"correct"选择两个元素中最小值的例子：
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 生成列表，并且 re-write 您的 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).