N-Queens / Erlangを並列化

した。おとといのC++版と同じ戦略で。とても簡単 :-)
プログラムはすぐ並列化できたけど、Mac PortsでインストールしたErlangがsmpに対応してないでやんの。
仕方が無いので、ソースをダウンロードしてきて、再make orz
% ./configure --enable-smp-support
% make
でOK。

で、実行してみると、答えはあってるし、大体半分くらいの時間で終わるんだけど、計測した時間が変？
逐次版で、1122とかでるところが、並列版でも1182とかでるし、たまに4098とか出る。timer:tcでの計測は駄目？

ググって、

go(N)-> 
	T1 = erlang:now(),
	Res = count(qu(N)),
	T2 = erlang:now(),
	Time = timer:now_diff(T2, T1),
	{Time,Res}.

とかやってる人を見つけたので、これで計測。
すると、

• 逐次版：10179827とか：１０秒ってところか？
• 並列版：5783055とか：5.7秒くらい？

というわけで、まずまず。（時計の秒針を見ての）体感もこれくらいだから、あってるんだろう、多分。

並列化した（=spawnを使った）プログラムは下記の通り。別に大した差はないです。
関数の引数にself()で取得した自プロセスのPidを渡してspawnし、spawnされたプロセスは結果を引数のPidで示されるプロセスに"!"で送ります。spawnした方のプロセスは、結果が欲しい時点で、receiveを使って計算結果をもらうと。

-module(qupar).
-export([qu/1, qudist/4, go/1, count/1]).

%go(N) -> timer:tc(qu,count,[qu(N)]).
go(N)-> 
	T1 = erlang:now(),
	Res = count(qu(N)),
	T2 = erlang:now(),
	Time = timer:now_diff(T2, T1),
	{Time,Res}.


count(C) -> count(C,0).
count([_H|T],Crnt) -> count(T,Crnt+1);
count([],Crnt) -> Crnt.

append([A|X],Y) -> [A|append(X,Y)];
append([],Y) -> Y.

qu(N) ->
      spawn(qupar,qudist,[generate(N), [], [], self()]),
      receive
        Ans -> Ans
      end.

generate(N) ->
        if N > 0 -> [N|generate(N - 1)];
           N == 0 -> []
        end.

qudist([P|Lu],Ls,Lp,Pid) -> 
	spawn(qupar,qudist,[Lu,[P|Ls],Lp,self()]),
        Lr = append(Lu,Ls),
        Ans1 = check(P,1,Lr,Lp,Lp),
	receive
	  Ans2 -> Ans = append(Ans1, Ans2)
        end, 
	Pid ! Ans;
qudist([],[_|_],_,Pid) -> Pid ! [];
qudist([],[],Lp,Pid) -> Pid ! [Lp].

qu([P|Lu],Ls,Lp) -> 
        Lr = append(Lu,Ls),
        Ans1 = check(P,1,Lr,Lp,Lp),
        Ans2 = qu(Lu,[P|Ls],Lp),
        append(Ans1, Ans2);
qu([],[_|_],_) -> [];
qu([],[],Lp) -> [Lp].

check(P,D,L,[Q|Lp0],Lp) ->
        if (Q + D == P) or (Q - D == P) -> [];
           true -> D1 = D + 1, check(P,D1,L,Lp0,Lp)
	end;
check(P,_,L,[],Lp) -> qu(L,[],[P|Lp]).