クイックソート - みずぴー日記

30分プログラム、その121。Erlangで並行に計算するクイックソート。

ピポットの右と左を別のプロセスで計算してから、あとから結合するようにしてみた。
でも、普通のクイックソートに負けている気がする。

使い方

> qsort:qsort([]).
[]

> qsort:qsort([3,2,1]).
[1,2,3]

あと、ベンチマーク用の関数も作った。それぞれ、CPU時間と経過時間を計測。対象とするリストは、すでにソート済のものを使用。

> qsort:bench(1000).
time 200(314) ms 
ok
> qsort:bench(2000).
time 490(745) ms 
ok
4> qsort:bench(3000).
time 950(1370) ms 
ok
5> qsort:bench(4000).
time 1560(2249) ms 
ok

あれ?O(N^2)で増加してる?それに、RubyのArray#sortより全然遅い。

ソースコード

-module(qsort).
-compile(export_all).

split(P,L) ->
    {[X || X<-L,X <  P],
     [X || X<-L,X >= P]}.

wait(Pid) -> 
    receive 
	{Pid,X} -> X;
	Any -> exit(Any)
    end.

send(L) ->
     Pid  = spawn(fun qsort/0),
     Pid ! {self(),L},
     Pid.

qsort() ->
    receive
 	{Pid,[]} ->
 	    Pid ! {self(),[]};
 	{Pid,[P|T]} -> 
	    {Lhs,Rhs} = split(P,T),
 	    Pid ! {self(),wait(send(Lhs)) ++ [P] ++wait(send(Rhs))};
	Any -> exit(Any)
    end.

qsort(L)->
    wait(send(L)).

bench(N)->
    statistics(runtime),
    statistics(wall_clock),
    qsort(lists:seq(0,N)),
    {_,Time1} = statistics(runtime),
    {_,Time2} = statistics(wall_clock),
    io:format("time ~p(~p) ms ~n",[Time1,Time2]).

参考

過去の30分プログラム