OddEvenソート リファクタリングしてみた
かなり無駄が多かったので修正してみた。あーんど、コメント入れてみた。
少しは読みやすくなったかも。
%% Author: tkuro %% Created: 2009/11/12 %% Description: odd-even parallel sort -module(oddeven_par). %% %% Include files %% -include_lib("eunit/include/eunit.hrl"). %% %% Exported Functions %% -export ([sort/1]). %% -------------------------------------------------------------------- %% Test Functions %% -------------------------------------------------------------------- sort_test_() -> [ ?_assertEqual(sort([1,3,2]),[1,2,3]), ?_assertEqual(sort([3,2,0,1,5,8,4,2,2,7]),[0,1,2,2,2,3,4,5,7,8]) ]. %% -------------------------------------------------------------------- %% Func: sort/1 %% Returns: sorted list %% -------------------------------------------------------------------- sort(L) -> make_proc_array(L). make_proc_array(L) -> make_proc_loop(none, L, true, length(L)). make_proc_loop(Last, [], _, _) -> Last ! {rememberme, last}, % kick the tail guy Last ! report, % ask him to inform beforehand gather([]); % gather report make_proc_loop(Left, [H|T], Side, N) -> S = self(), Pid = spawn_link(fun () -> sorter(S, {Left, none}, H, Side, N) end), make_proc_loop(Pid, T, not(Side), N). % gather report from processes (reduce) gather(Acc) -> receive fin -> Acc; Val -> gather([Val|Acc]) end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% sofrter node definition %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%% % sending primary link request sorter(S, {Left, none}, Val, Side, N) -> push(Left, fun(Pid)-> Pid ! {rememberme, self()} end), receive {rememberme, R} -> % and receive Right Pid sorter(S, {Left, R}, Val, Side, N) end; % finish sorting sorter(S, Nbrs, Val, _, 0) -> case Nbrs of {none, _} -> % I am the head (the last guy) receive report -> S ! Val, % inform value to the boss S ! fin % I am responsible to inform finale end; {Left, _} -> % I am a normal guy receive report -> S ! Val, % inform value to the boss Left ! report % ask next to report end end; % normal mode sorter(S, Nbrs, Val, Side, N) -> {Left, Right} = Nbrs, Dir = if Side -> Right; true -> Left end, % which way? NSide = not(Side), % toggle case push(Dir, fun(Pid)-> Pid! {push, self(), Val} end ) of cantpush -> sorter(S, Nbrs, Val, NSide, N-1); % no pair _ -> void end, receive {push, Dir, HisVal} -> case Val > HisVal andalso Dir =:= Left orelse HisVal > Val andalso Dir =:= Right of true -> sorter(S, Nbrs, Val, NSide, N-1); % no change false -> sorter(S, Nbrs, HisVal, NSide, N-1) % exchange end end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% utilities push(Pid, F) -> case Pid =/= last andalso Pid =/= none of true -> F(Pid); false-> cantpush end.
追記: 11/14 ちょっと修正