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

问题描述

我正在尝试使用Bubblesort在Prolog中对10k元素列表进行排序，但出现了本地堆栈错误.合并排序似乎是最好的选择，因为相同的输入没有任何错误.但是，我真的很想为带有大量输入数据的Bubblesort运行时间，但我做不到.有什么想法吗?

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?

推荐答案

由于有两个答案，而且没有人足够明确地指出您陷入脱离本地堆栈"麻烦的原因(马特在评论中表示:您的问题是谓词不是确定性的，但没有确切解释原因.

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.

您可以使用称为 lagging 的技术来解决此问题:

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 的含义将取决于实现，但是通常，当所有子句的第一个参数都是具有不同 functors 的所有术语时，则不会创建选择点.

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, 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屋！