急に思い立ってerlangで素数リストを求めるプログラムを書いた。
エラトステネスのふるい
まずは基本的なプログラミング。関数prime()は再帰的にsqrt(N)回実行する。
# cat prime1.erl -module(prime1). -export([getl/1, checkp/1]). %% Nまでの素数リストを返す getl(1) -> []; getl(2) -> [2]; getl(N) -> prime(trunc(math:sqrt(N)), [2], lists:seq(3,N,2)). %% prime(Max:最大実行回数、P:素数リスト、[H|T]:3からNまでの奇数のリスト) prime(Max, P, [H|T]) -> if H > Max -> P ++ [H|T]; true -> prime(Max, P ++ [H], lists:filter(fun(X) -> (X rem H) =/= 0 end, T)) end. %% Nが素数かどうかチェック checkp(N) -> (lists:last(getl(N)) =:= N).
実行は以下のとおり。
# erl Erlang R16B02 (erts-5.10.3) [source] [smp:2:2] [async-threads:10] [hipe] [kernel-poll:false] Eshell V5.10.3 (abort with ^G) 1> c(prime1). {ok,prime1} 2> prime1:getl(10). [2,3,5,7] 3> prime1:getl(20). [2,3,5,7,11,13,17,19] 4> prime1:getl(100). [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73, 79,83,89,97] 5> prime1:checkp(97). true 6> prime1:checkp(99). false
サーバ化
次、サーバ化する。
# cat prime2.erl -module(prime2). -export([start/0, check/2, get/2]). %% %% クライアント %% get(Pid, N) -> rpc(Pid, {get, N}). check(Pid, N) -> rpc(Pid, {check, N}). rpc(Pid, {Type, Val}) -> Pid ! {self(), {Type, Val}}, receive Responce -> Responce end. %% %% サーバ %% start() -> spawn(fun loop/0). loop() -> receive {FROM, {get, N}} -> FROM ! getl(N), loop(); {FROM, {check,N}} -> FROM ! checkp(N), loop() end. %% Nまでの素数リストを返す getl(1) -> []; getl(2) -> [2]; getl(N) -> prime(trunc(math:sqrt(N)), [2], lists:seq(3,N,2)). %% prime(Max:最大実行回数、P:素数リスト、[H|T]:3からNまでの奇数のリスト) prime(Max, P, [H|T]) -> if H > Max -> P ++ [H|T]; true -> prime(Max, P ++ [H],lists:filter(fun(X) -> (X rem H) =/= 0 end, T)) end. %% Nが素数かどうかチェック checkp(N) -> (lists:last(getl(N)) =:= N).
実行例。最後に1000000までの素数リストを計算させる。数10秒くらいかかる。
# erl Erlang R16B02 (erts-5.10.3) [source] [smp:2:2] [async-threads:10] [hipe] [kernel-poll:false] Eshell V5.10.3 (abort with ^G) 1> c(prime2). {ok,prime2} 2> Pid = prime2:start(). <0.40.0> 3> prime2:get(Pid, 10). [2,3,5,7] 4> prime2:get(Pid, 20). [2,3,5,7,11,13,17,19] 5> prime2:check(Pid, 20). false 6> prime2:check(Pid, 19). true 7> prime2:get(Pid, 10000000). [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73, 79,83,89,97,101,103,107,109|...] 8> length(prime2:get(Pid, 10000000)). 664579
サーバにキャッシュ機能をいれる
キャッシュ化の元ネタはこちら。
ただし、こちらはfoldlを使って2からNまでチェックする。
他方、ここで書いたふるいの方法はprime()の再帰呼び出しでsqrt(N)回のチェックで済ませる。よって、実行時間は相当短縮できている。
# cat prime3.erl -module(prime3). -export([start/0, check/2, get/2]). %% %% クライアント %% get(Pid, N) -> rpc(Pid, {get, N}). check(Pid, N) -> rpc(Pid, {check, N}). rpc(Pid, {Type, Val}) -> Pid ! {self(), {Type, Val}}, receive Responce -> Responce end. %% %% キャッシュ機能付きサーバ %% start() -> spawn(fun() -> loop(2,[2]) end). %% L := Checkedまでの素数リスト loop(Checked, L) -> receive {FROM, {get, N}} -> Ret = getl(N, Checked, L), FROM ! Ret; {FROM, {check, N}} -> Ret = getl(N, Checked, L), %% 関数checkp()は廃止、素数リストの末尾を比較 FROM ! (lists:last(Ret) =:= N) end, loop(max(Checked, N), (if (length(Ret) < length(L)) -> L; true -> Ret end)). %% Nまでの素数リストを返す getl(1, _, _) -> []; getl(N, Checked, L) -> if N =< Checked -> %% すでに求めた素数リストLから返す lists:filter(fun(X) -> X =< N end, L); true -> %% すでに求めた素数リストに、Nまでの整数リストを追加 prime(trunc(math:sqrt(N)), [], L ++ lists:seq(Checked,N)) end. %% prime(Max:最大実行回数、P:素数リスト、[H|T]:2からNまでの整数のリスト) prime(Max, P, [H|T]) -> if H > Max -> P ++ [H|T]; true -> prime(Max, P ++ [H],lists:filter(fun(X) -> (X rem H) =/= 0 end, T)) end.
実行方法は上と同じ。大きな数値を入力すると、最初は時間がかかる。
しかし次に実行するとキャッシュされたリストを即、返す。
# erl Erlang R16B02 (erts-5.10.3) [source] [smp:2:2] [async-threads:10] [hipe] [kernel-poll:false] Eshell V5.10.3 (abort with ^G) 1> c(prime3). {ok,prime3} 2> Pid = prime3:start(). <0.34.0> 3> prime3:get(Pid, 10000000). [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73, 79,83,89,97,101,103,107,109|...] 4> prime3:get(Pid, 10000000). [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73, 79,83,89,97,101,103,107,109|...] 5> length(prime3:get(Pid, 10000000)). 664579 6> length(prime3:get(Pid, 1200000)). 92938 7> length(prime3:get(Pid, 12000000)). 788060
