並列マージソート

30分プログラム、その738。並列版のマージソートを書いてみました。
積読置き場からマルチコアCPUのための並列プログラミングが発掘されたので、そこにのっていた並列マージソートのアルゴリズムを実装してみました。

• 分割するたびにスレッドを生成する
• ただし、生成するスレッドの数には上限がある
• 上限をを越えたら、それ以降はクイックソートする

という感じのアルゴリズムらしいです。分割数に上限があるのがポイントですね。

使い方

1> merge:msort(2, [10,3,2,1]).
[1,2,3,10]

ソースコード

-module(merge).
-compile([export_all]).

qsort([]) ->
    [];
qsort([H | Tl]) ->
    qsort([ X || X <- Tl, X < H])
    ++ [ H ]
    ++ qsort([ X || X <- Tl, X >= H]).

merge(Xs,[]) ->
    Xs;
merge([],Ys) ->
    Ys;
merge([X | Xs], [Y | _] = Ys) when X < Y ->
    [ X | merge(Xs, Ys)];
merge([X | _ ] = Xs, [Y | Ys]) when X >= Y ->
    [ Y | merge(Xs, Ys)].

split([]) ->
    {[],[]};
split([ X ]) ->
    {[ X ], []};
split([ X , Y | Tl]) ->
    { Xs, Ys} = split(Tl),
    { [ X | Xs ], [ Y | Ys ]}.

msort(Pid, 0, Xs) ->
    Pid ! {ok, qsort(Xs)};
msort(Pid, _, []) ->
    Pid ! {ok, []};
msort(Pid, N, Xs) ->
    Self = self(),
    {Ys, Zs} = split(Xs),
    spawn(fun () -> msort(Self, N-1, Ys) end),
    spawn(fun () -> msort(Self, N-1, Zs) end),
    receive {ok, A} ->
      receive {ok, B} ->
	      Pid ! {ok, merge(A, B)}
      end
    end.

msort(N, Xs) ->
    Self = self(),
    spawn(fun () -> msort(Self, N, Xs) end),
    receive
      {ok, A} -> A
    end.

参考

• 過去の30分プログラム
• マルチコアCPUのための並列プログラミング