在 Prolog 中对大型列表进行排序:内存不足 [英] Sorting large lists in Prolog: Not enough memory

问题描述

我正在尝试使用bubblesort 对prolog 中的10k 元素列表进行排序，但出现本地堆栈错误.Mergesort 似乎是最好的选择，因为对于相同的输入，我没有收到任何错误.但是，我真的很想为具有大量输入数据的冒泡排序获得一些运行时间，但我做不到.有什么想法吗?

I'm trying to sort a 10k element list in prolog with bubblesort and I get the out of local stack error. Mergesort seems to be the best option since I don't get any errors for the same input. However I'd really like to get some running times for bubblesort with large input data but I can't. Any ideas?

代码如下:

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

如您所见，我正在使用尾递归.我还尝试使用以下方法扩大堆栈:

As you can I see I'm using tail recursion. I've also tried enlarging the stacks by using:

  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 列表还是不使用递归?

but it just runs for a bit longer. Eventually I get out of local stack again. Should I use another language like C and malloc the list or not use recursion?

推荐答案

既然有两个答案，没有人足够明确地指出你遇到本地堆栈外"问题的原因(Mat 在评论中说你的问题是你的谓词不是确定性的，但没有确切解释为什么).

Since there are two answers, and no one pointed out explicitly enough the reason why you get into "out of local stack" trouble (Mat says in the comment to your question that your predicates are not deterministic, but does not explain exactly why).

您定义的两个谓词，即 bubblesort/3 和 bubble/3，具有互斥子句.但是 Prolog(至少 SWI-Prolog)不承认这些是相互排斥的.因此，创建了选择点，您没有得到尾递归优化，并且可能没有垃圾收集(如果您想知道何时何地去了多少，您需要使用您选择的实现来衡量).

Two of the predicates you have defined, namely, bubblesort/3 and bubble/3, have mutually exclusive clauses. But Prolog (at least SWI-Prolog) does not recognize that these are mutually exclusive. So, choice points are created, you don't get tail recursion optimization, and probably no garbage collection (you need to measure using your implementation of choice if you want to know how much goes where and when).

你有两个不同的问题.

这个问题在两个谓词中都会出现.在最简单的谓词中:

This problem pops up in both predicates. In the most simple predicate possible:

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

然后:

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

这并不奇怪；考虑:

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

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

You can solve this by using a technique called lagging:

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

然后:

?- bar([a]).
true.

在bar_1/2的定义中，第一个子句的第一个参数是空列表；第二个子句的第一个参数是一个非空列表(一个至少有一个元素和一个尾部的列表).当所有子句明显排他时，Prolog 不会创建选择点.obvious 的含义取决于实现，但通常，当所有子句的第一个参数都是具有不同 functor 的术语时，不会创建选择点.

In the definition of bar_1/2, the first argument to the first clause is the empty list; the first argument to the second clause is a non-empty list (a list with at least one element, and a tail). Prolog does not create choice points when all clauses are obviously exclusive. What obvious means will depend on the implementation, but usually, when the first arguments to all clauses are all terms with different functors, then no choice points are created.

尝试以下方法(您可能会得到不同的结果，但信息是相同的):

Try the following (you might get different results, but the message is the same):

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

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

请参阅 这个问题 和 Mat 的回答，看看如何您可以使用它来使您的程序具有确定性.

See this question and the answer by Mat to see how you can use this to make your program deterministic.

如果我没看错的话，Mat 在他的回答中使用了这种方法.

Mat, in his answer, uses this approach, if I see correctly.

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

This is the problem with the second and third clause of bubble/3. In the textbook "correct" example of choosing the minimum of two elements:

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.

You can solve this in two ways: either by doing what Mat is doing, which is, using compare/3, which succeeds deterministically; or, by doing what CapelliC is doing, which is, using an 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
    ).

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

I know there will always be at least as many opinions as heads, but both are fine, depending on what you are doing.

您可以使用内置的 length/2 生成一个列表，然后像这样重写您的 generate_list/3:

You could use the built in length/2 to generate a list, and re-write your generate_list/3 like this:

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 表示:

The helper random_pos_ints/2 is a trivial predicate that can be expressed in terms of maplist:

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

这篇关于在 Prolog 中对大型列表进行排序:内存不足的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！