首页 > Erlang并发教程 > 4.5 Erlang并发编程-常用列表处理函数sort
2013
11-06

4.5 Erlang并发编程-常用列表处理函数sort

sort

程序3.1是著名的快速排序的一个变体。sort(X)对列表X的元素排序,将结果放入一个新列表并将之返回。

程序3.1

-module(sort).
-export([sort/1]).

sort([]) -> [];
sort([Pivot|Rest]) ->
    {Smaller, Bigger} = split(Pivot, Rest),
    lists:append(sort(Smaller), [Pivot|sort(Bigger)]).

split(Pivot, L) ->
    split(Pivot, L, [], []).

split(Pivot, [], Smaller, Bigger) ->
    {Smaller,Bigger};
split(Pivot, [H|T], Smaller, Bigger) when H > Pivot ->
    split(Pivot, T, [H|Smaller], Bigger);
split(Pivot, [H|T], Smaller, Bigger) when H >= Pivot ->
    split(Pivot, T, Smaller, [H|Bigger]).

此处选取列表的第一个元素为中轴。元列表被分为两个列表SmallerBiggerSmaller的所有元素都小于中轴PivotBigger的所有元素都大于等于Pivot。之后,再对列表SmallerBigger分别排序并将结果合并。

函数split({Pivot, L})返回元组{Smaller, Bigger},其中所有Bigger中的元素都大于等于Pivot而所有Smaller中的元素都小于Pivotsplit(Pivot, L)通过调用一个辅助函数split(Pivot, L, Smaller, Bigger)完成任务。两个累加列表,SmallerBigger分别用于存储L中小于和大于等于Pivot的元素。split/4的代码与reverse/2非常相像,只是多用了一个累加列表。例如:

> lists:split(7,[2,1,4,23,6,8,43,9,3]).
{[3,6,4,1,2],[9,43,8,23]}

如果我们调用sort([7,2,1,4,23,6,8,43,9,3]),首先就会以7为中轴来调用split/2。这将产生两个列表:所有元素都小于中轴7[3,6,4,1,2],以及所有元素都大于等于中轴的[9,43,8,23]

假设sort工作正常,则sort([3,6,4,1,2])[1,2,3,4,6]sort([9,43,8,23])[8,9,23,43]。最后,排好序的列表被拼装在一起:

> append([1,2,3,4,6], [7 | [8,9,23,43]]).
[1,2,3,4,6,7,8,9,23,43]

再动一点脑筋,都append的调用也可以省掉,如下所示:

qsort(X) ->
    qsort(X, []).

%% qsort(A,B)
%%   Inputs:
%%      A = unsorted List
%%      B = sorted list where all elements in B
%%          are greater than any element in A
%%   Returns
%%      sort(A) appended to B

qsort([Pivot|Rest], Tail) ->
    {Smaller,Bigger} = split(Pivot, Rest),
    qsort(Smaller, [Pivot|qsort(Bigger,Tail)]);
qsort([], Tail) ->
    Tail.

我们可以利用BIFstatistics/1(用于提供系统性能相关的信息,参见附录??)将之与第一版的sort做一个对比。如果我们编译并执行以下代码片段:

...
statistics(reductions),
lists:sort([2,1,4,23,6,7,8,43,9,4,7]),
{_, Reductions1} = statistics(reductions),
lists:qsort([2,1,4,23,6,7,8,43,9,4,7]),
{_, Reductions2} = statistics(reductions),
...

我们可以得知sortqsort的归约(函数调用)次数。在我们的示例中sort花费93次归约,而qsort花费74次,提升了百分之二十。


4.5 Erlang并发编程-常用列表处理函数sort》有 1 条评论

  1. lovefang 说:

    上面程序 3.1下面那段代码 你打错了一个符号split(Pivot, [H|T], Smaller, Bigger) when H > Pivot -> %% 这里 应该是 H < Pivot split(Pivot, T, [H|Smaller], Bigger);split(Pivot, [H|T], Smaller, Bigger) when H >= Pivot -> split(Pivot, T, Smaller, [H|Bigger]).

留下一个回复

你的email不会被公开。