Prolog 中的排序谓词

Question

我想弄清楚 sort/2 在 Prolog 中是如何实现的。我想看看它是如何工作的，但我无法在任何地方找到它的代码。有人知道它是如何实现的吗？

Answer 1

在 SWI-Prolog 中，sort/2 是一个“内置”，所以它在 C 中。

该文件似乎是 src/pl-lists.c 的分布。

这里是：

https://github.com/SWI-Prolog/swipl-devel/blob/master/src/pl-list.c

第 543 行：

static
PRED_IMPL("sort", 2, sort, PL_FA_ISO)
{ PRED_LD

  return pl_nat_sort(A1, A2,
             TRUE, SORT_ASC,
             0, NULL, FALSE PASS_LD);
}

pl_nat_sort 在同一个文件中

该评论具有历史意义：

Natural merge sort. Code contributed by Richard O'Keefe and integrated into SWI-Prolog by Jan Wielemaker. The nice point about this code is that it uses no extra space and is pretty stable in performance. Richards claim it that many qsort() implementations in libc are very slow. This isn't the case for glibc 2.2, where this performs about the same as the previous qsort() based implementation.

理查德·奥基夫大概指出：

I've been using a variant of this code in a sorting utility since about 1988. It leaves the UNIX sort(1) program in the dust. As you may know, sort(1) breaks the input into blocks that fit in memory, sorts the blocks using qsort(), and writes the blocks out to disc, then merges the blocks. For files that fit into memory, the variant of this code runs about twice as fast as sort(1). Part of that is better I/O, but part is just plain not using qsort().

日姆。这带回了 89 年编写排序算法的记忆。

Answer 2

尝试搜索快速排序。

这是一个link：https://www.codepoc.io/blog/prolog/4934/prolog-program-to-sort-a-list-using-quick-sort

这是另一个例子：-

quicksort([], []).
quicksort([X | Tail], Sorted):-
    split(X, Tail, Small, Big),
    quicksort(Small, SortedSmall),
    quicksort(Big, SortedBig),
    concatenate(SortedSmall, [X| SortedBig], Sorted).

split(X, [], [], []).
split(X, [Y| Tail], [Y | Small], Big):-
    X > Y, !,
    split(X, Tail, Small, Big).
split(X, [Y| Tail], Small, [Y | Big]):-
    split(X, Tail, Small, Big).

concatenate([],List,List).
concatenate([Item|List1],List2,[Item|List3]) :-
    concatenate(List1,List2,List3).


?-quicksort([1,7,4,3,6,5,9,8,12,1],L).
L = [1, 1, 3, 4, 5, 6, 7, 8, 9, 12]
false

Answer 3

如果你只是想搜索任何排序算法，你总是可以使用 bubblesort *咳咳*。这是对列表进行排序的最简单和最低效的方法之一，但是 - 根据实现 - 将运行在线性时间内通过一个已经排序的列表。 Bubblesort 不会删除重复项。此实现按降序排列：

bubblesort(List, SortedList) :-
    bubbleit(List, List1), 
    ! ,
    bubblesort(List1, SortedList) .
bubblesort(List, List).

bubbleit([X,Y|Rest], [Y,X|Rest]) :-
    X < Y, 
    ! .
bubbleit([Z|Rest], [Z|Rest1]) :-
    bubbleit(Rest, Rest1).

?- bubblesort([1,2,5,4,7,3,2,4,1,5,3],L).
L = [7, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1].

如果要对列表中的第二个元素进行排序 [_,E|] 将第一个 bubbleit 规则更改为

bubbleit([X,Y|Rest], [Y,X|Rest]) :-
    X = [_,XX|_],
    Y = [_,YY|_],
    XX < YY, 
    ! .

?- bubblesort([[a,3],[b,5],[c,1],[d,4]],L).
L = [[b, 5], [d, 4], [a, 3], [c, 1]].

Answer 4

合并排序 算法非常适合 Prolog。更不用说用递归和列表作为基础的语言实现微不足道了。

这是一个 SWI 游乐场：https://swish.swi-prolog.org/p/swi-prolog-merge-sort.pl

merge_sort( [], [] ).             % The empty list is by definition ordered
merge_sort( [X], [X] ).           % So is a list of length one
merge_sort( Unsorted, Sorted ) :- % otherwise...
  partition( Unsorted, L, R ) ,   % partition the list into 2 halves
  merge_sort(L,L1),               % recursively sort the left half
  merge_sort(R,R1),               % recursively sort the right half
  merge(L1,R1,Sorted)             % merge the newly-sorted halves
    .                             % See? simple!

partition( []      , []     , []     ).   % the empty list gets partitioned into two empty lists
partition( [X]     , [X]    , []     ).   % a left of length 1 gets partitioned into itself and an empty list
partition( [X,Y|L] , [X|Xs] , [Y|Ys] ) :- % list of length 2 or more gets popped and divided between left and right halves
  partition(L,Xs,Ys)                      % with the remainder being recursively partitioned.
    .                                     % Easy!

merge( []     , []     , []     ).        % merging to empty lists is trivial
merge( []     , [Y|Ys] , [Y|Ys] ).        % merging an empty list and a non-empty list is easy
merge( [X|Xs] , []     , [X|Xs] ).        % merging a non-empty list and an empty list is easy
merge( [X|Xs] , [Y|Ys] , [Lo,Hi|Zs] ) :-  % otherwise...
  compare(X,Y,Lo,Hi),                     % compare the two terms, put them in collating sequence
  merge(Xs,Ys,Zs)                         % and recursively merge the tails
  .                                       % Easy!

compare( X , Y , X, Y ) :- X @=< Y. % if X <= Y, X is Lo, and Y is Hi
compare( X , Y , Y, X ) :- X @>  Y. % if X >  Y, Y is Lo, and X is Hi

Prolog 中的排序谓词

Sort predicate in Prolog

prolog

swi-prolog