8.11の練習問題。これ本の中には答え載ってないのかな…？
自分なりの回答。時間計測部分のコードは省略。
- コードの簡潔さを優先してリングの”始点”は固定にした
- リストを配列代わりに使っているので効率が悪い
-module(ring_server0). -export([construct/1, start/3, prepare/2]). nth0(I, L) -> lists:nth(I+1, L). rpc(Pid, Request) -> Pid ! {self(), Request}, receive {Pid, Response} -> Response end. construct(N) when N > 0 -> Pids = lists:map(fun(I) -> spawn(?MODULE, prepare, [self(), I]) end, lists:seq(1, N)), lists:foreach(fun(I) -> Pid = nth0(I, Pids), Prev = nth0((I-1+N) rem N, Pids), Next = nth0((I+1) rem N, Pids), Pid ! {self(), {Prev, Next}} end, lists:seq(0, N-1)), nth0(0, Pids). prepare(Builder, Pos) -> receive {Builder, {Prev, Next}} -> loop(Pos, Prev, Next) end. loop(1, Prev, Next) -> receive {_, {0, Msg, Client}} -> %io:format("finishi rotation of ~p~n", [Msg]), Client ! {self(), Msg}, loop(1, Prev, Next); {_, {M, Msg, Client}} -> %io:format("last ~p rotations of ~p~n", [M, Msg]), Next ! {self(), {M-1, Msg, Client}}, loop(1, Prev, Next) end; loop(Pos, Prev, Next) -> receive {Prev, {_M, Msg, Client}=Req} -> %io:format("pass ~p to the next node ~p~n", [Msg, Next]), Next ! {self(), Req}, loop(Pos, Prev, Next) end. start(Pid, M, Msg) when M >= 0 -> rpc(Pid, {M, Msg, self()}).
実行時間の計測。
N=100, M=100 time=0.01, (0.008) seconds N=10000, M=10 time=10.55, (10.925) seconds N=10, M=10000 time=0.06, (0.058) seconds
…遅い！明らかにリングの構築部分がボトルネックになっている。効率が悪いことは分かっていたが、これほどとは。
やっぱり線形アクセスじゃいけねえ、ということでこのあたりを見ながらdictを使って construct/1 を書き直し。
construct(N) when N > 0 -> Pids = dict:from_list( lists:map(fun(I) -> {I-1, spawn(?MODULE, prepare, [self(), I])} end, lists:seq(1, N))), lists:foreach(fun(I) -> Pid = Pids:fetch(I), Prev = Pids:fetch((I-1+N) rem N), Next = Pids:fetch((I+1) rem N), Pid ! {self(), {Prev, Next}} end, lists:seq(0, N-1)), Pids:fetch(0).
劇的に改善された。
N=100, M=100 time=0.0, (0.007) seconds N=10000, M=10 time=0.2, (0.228) seconds N=10, M=10000 time=0.06, (0.058) seconds
[...] ring_constructor_list.sh 一番最初に作ったリストによる実装。クソ遅い。 [...]