erlang - アーランのエラトステネスのふるい

Question

Erlangを勉強中です。演習として、素数を生成するエラトステネスのふるいアルゴリズムを取り上げました。これが私のコードです：

-module(seed2).
-export([get/1]).

get(N) -> WorkList = lists:duplicate(N, empty),
          get(2, N, WorkList, []).

get(thats_the_end, _N, _WorkList, ResultList) -> lists:reverse(ResultList);
get(CurrentPrime, N, WorkList, ResultList) -> ModWorkList = markAsPrime(CurrentPrime, N, WorkList),
                                              NextPrime = findNextPrime(CurrentPrime + 1, N, WorkList),
                                              get(NextPrime, N, ModWorkList, [CurrentPrime|ResultList]).


markAsPrime(CurrentPrime, N, WorkList) when CurrentPrime =< N -> WorkListMod = replace(CurrentPrime, WorkList, prime),
                                                                 markAllMultiples(CurrentPrime, N, 2*CurrentPrime, WorkListMod).

markAllMultiples(_ThePrime, N, TheCurentMark, WorkList) when TheCurentMark > N -> WorkList;
markAllMultiples(ThePrime, N, TheCurrentMark, WorkList) -> WorkListMod = replace(TheCurrentMark, WorkList, marked),
                                                           markAllMultiples(ThePrime, N, TheCurrentMark + ThePrime, WorkListMod).

findNextPrime(Iterator, N, _WorkList) when Iterator > N -> thats_the_end;
findNextPrime(Iterator, N, WorkList) -> I = lists:nth(Iterator, WorkList),
                                        if
                                          I =:= empty -> Iterator;
                                          true -> findNextPrime(Iterator + 1, N, WorkList)
                                        end.

replace(N, L, New)-> {L1, [_H|L2]} = lists:split(N - 1, L),
                     lists:append(L1, [New|L2]).

このコードは実際に機能します:)。問題は、それが可能な限り最良の実装ではないと私が感じていることです。

私の質問は、「エラトステネスのふるい」を実装する「エルラン語」の方法は何であるかということです

編集:OK、アンドレアスのソリューションは非常に優れていますが、遅いです。それを改善する方法はありますか？

score 13 · Accepted Answer

以下は、単純な (しかしそれほど高速ではない) ふるいの実装です。

-module(primes).
-export([sieve/1]).
-include_lib("eunit/include/eunit.hrl").

sieve([]) ->
    [];
sieve([H|T]) ->          
    List = lists:filter(fun(N) -> N rem H /= 0 end, T),
    [H|sieve(List)];
sieve(N) ->
    sieve(lists:seq(2,N)).

score 9 · Accepted Answer

これは、リスト内包表記を使用し、末尾再帰を試みる私のふるいの実装です。素数がソートされるように、最後にリストを逆にします。

primes(Prime, Max, Primes,Integers) when Prime > Max ->
    lists:reverse([Prime|Primes]) ++ Integers;
primes(Prime, Max, Primes, Integers) ->
    [NewPrime|NewIntegers] = [ X || X <- Integers, X rem Prime =/= 0 ],
    primes(NewPrime, Max, [Prime|Primes], NewIntegers).

primes(N) ->
    primes(2, round(math:sqrt(N)), [], lists:seq(3,N,2)). % skip odds

私の 2 GHz の Mac で 2 ミルまでの素数を計算するには、約 2.8 ミリ秒かかります。

score 2 · Accepted Answer

2

並行処理を使用して問題に取り組みました。

ソース

于 2008-09-28T20:14:22.570 に答える

score 2 · Accepted Answer

以前の投稿が正しくフォーマットされていませんでした。ここにコードの再投稿があります。スパムでごめんなさい…


-module(test).

%%-export([sum_primes/1]).
-compile(export_all).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%Sum of all primes below Max. Will use sieve of Eratosthenes 
sum_primes(Max) ->
    LastCheck = round(math:sqrt(Max)),
    All = lists:seq(3, Max, 2), %note are creating odd-only array
    %%Primes = sieve(noref,All, LastCheck),
    Primes = spawn_sieve(All, LastCheck),
    lists:sum(Primes) + 2. %adding back the number 2 to the list


%%sieve of Eratosthenes
sieve(Ref,All, LastCheck) ->
    sieve(Ref,[], All, LastCheck).

sieve(noref,Primes, All = [Cur|_], LastCheck) when Cur > LastCheck ->
    lists:reverse(Primes, All); %all known primes and all remaining from list (not sieved) are prime    
sieve({Pid,Ref},Primes, All=[Cur|_], LastCheck) when Cur > LastCheck ->
    Pid ! {Ref,lists:reverse(Primes, All)}; 
sieve(Ref,Primes, [Cur|All2], LastCheck) ->
    %%All3 = lists:filter(fun(X) -> X rem Cur =/= 0 end, All2),
    All3 = lists_filter(Cur,All2),
    sieve(Ref,[Cur|Primes], All3,  LastCheck).


lists_filter(Cur,All2) ->
    lists_filter(Cur,All2,[]).

lists_filter(V,[H|T],L) ->
    case H rem V of
    0 ->
        lists_filter(V,T,L);
    _ ->
        lists_filter(V,T,[H|L])
    end;
lists_filter(_,[],L) ->
    lists:reverse(L).


%% This is a sloppy implementation ;)
spawn_sieve(All,Last) ->
    %% split the job
    {L1,L2} = lists:split(round(length(All)/2),All),
    Filters = filters(All,Last),
    L3 = lists:append(Filters,L2),
    Pid = self(),
    Ref1=make_ref(),
    Ref2=make_ref(),
    erlang:spawn(?MODULE,sieve,[{Pid,Ref1},L1,Last]),
    erlang:spawn(?MODULE,sieve,[{Pid,Ref2},L3,Last]),
    Res1=receive
         {Ref1,R1} ->
         {1,R1};
         {Ref2,R1} ->
         {2,R1}
     end,
    Res2= receive
          {Ref1,R2} ->
          {1,R2};
          {Ref2,R2} ->
          {2,R2}
      end,
    apnd(Filters,Res1,Res2).


filters([H|T],Last) when H 
    [H|filters(T,Last)];
filters([H|_],_) ->
    [H];
filters(_,_) ->
    [].


apnd(Filters,{1,N1},{2,N2}) ->
    lists:append(N1,subtract(N2,Filters));
apnd(Filters,{2,N2},{1,N1}) ->
    lists:append(N1,subtract(N2,Filters)).



subtract([H|L],[H|T]) ->
    subtract(L,T);
subtract(L=[A|_],[B|_]) when A > B ->
    L;
subtract(L,[_|T]) ->
    subtract(L,T);
subtract(L,[]) ->
    L.

score 1 · Accepted Answer

十分に単純で、アルゴリズムを正確に実装し、ライブラリ関数を使用しません（パターンマッチングとリスト内包表記のみ）。確かに、それほど強力ではありません。私はそれをできるだけ単純にすることだけを試みました。

-module(primes).
-export([primes/1, primes/2]).

primes(X) -> sieve(range(2, X)).
primes(X, Y) -> remove(primes(X), primes(Y)).

range(X, X) -> [X];
range(X, Y) -> [X | range(X + 1, Y)].

sieve([X]) -> [X];
sieve([H | T]) -> [H | sieve(remove([H * X || X <-[H | T]], T))].

remove(_, []) -> [];
remove([H | X], [H | Y]) -> remove(X, Y);
remove(X, [H | Y]) -> [H | remove(X, Y)].

score 1 · Accepted Answer

上司にこれを見せることができます：http ：//www.sics.se/~joe/apachevsyaws.html 。そして、他のいくつかの（古典的な？）erlang引数は次のとおりです：

-ノンストップ操作、新しいコードをその場でロードできます。

-デバッグが簡単で、分析するコアダンプが不要です。

-マルチコア/CPUを利用しやすい

-クラスターを利用するのは簡単ですか？

-誰がポインタなどを扱いたいですか？これは21世紀ではありませんか？;）

いくつかの落とし穴：-何かを書くのは簡単で速いように見えるかもしれませんが、パフォーマンスは悪くなる可能性があります。何かを速くしたいのなら、私は通常、同じ関数の2〜4つの異なるバージョンを書くことになります。そして、多くの場合、使用されているものとは少し異なる可能性のある問題にタカの目でアプローチする必要があります。

リストで物事を検索する>約1000要素は遅いので、etsテーブルを使用してみてください。
文字列「abc」は、3バイトよりもはるかに多くのスペースを必要とします。したがって、バイナリを使用してみてください（これは面倒です）。

全体として、パフォーマンスの問題は、erlangで何かを書くときに常に心に留めておくべきことだと思います。Erlangの男はそれを解決する必要があります、そして私は彼らがそうするだろうと思います。

score 1 · Accepted Answer

私は素数というテーマが好きなので、BarryE のコードを少し変更し始め、独自のリストフィルター関数を作成して約 70% 高速化し、両方の CPU を利用できるようにしました。また、2 つのバージョン間で簡単に交換できるようにしました。テスト実行は次を示します。

61> timer:tc(test,sum_primes,[2000000])。
{2458537,142913970581}

コード：


-モジュール(テスト).

%%-export([sum_primes/1])。
-compile(export_all)。

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%％%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %
%%Max 未満のすべての素数の合計。エラトステネスの篩を使用します
sum_primes(最大) ->
    LastCheck = round(math:sqrt(Max)),
    All = lists:seq(3, Max, 2), %note は奇数のみの配列を作成しています
    %%Primes = sieve(noref,All, LastCheck),
    素数 = spawn_sieve(All, LastCheck),
    lists:sum(Primes) + 2. %数 2 をリストに追加し直す


%%エラトステネスのふるい
sieve(Ref,All, LastCheck) ->
    sieve(参照、[]、すべて、LastCheck)。

sieve(noref,Primes, All = [Cur|_], LastCheck) when Cur > LastCheck ->
    リスト：リバース（素数、すべて）; %すべての既知の素数とリストからの残りのすべて (ふるいにかけられていない) は素数です    
sieve({Pid,Ref},Primes, All=[Cur|_], LastCheck) when Cur > LastCheck ->
    ピッド！{Ref,lists:reverse(素数, すべて)};
sieve(Ref,Primes, [Cur|All2], LastCheck) ->
    %%All3 = lists:filter(fun(X) -> X rem Cur =/= 0 end, All2),
    All3 = lists_filter(Cur,All2),
    sieve(Ref,[Cur|Primes], All3, LastCheck)。


list_filter(Cur,All2) ->
    list_filter(Cur,All2,[])。

lists_filter(V,[H|T],L) ->
    ケース H レム V の
    0 ->
        リスト_フィルター(V、T、L);
    _ ->
        lists_filter(V,T,[H|L])
    終わり;
lists_filter(_,[],L) ->
    リスト：リバース（L）。



%% これはずさんな実装です ;)
spawn_sieve(すべて、最後) ->
    %% ジョブを分割します
    {L1,L2} = リスト:スプリット(丸め(長さ(すべて)/2),すべて),
    フィルター = フィルター (すべて、最後)、
    %%io:format("F:~p~n",[フィルタ]),
    L3 = リスト:append(フィルタ,L2),
    %%io:format("L1:~w~n",[L1]),
    %% io:format("L2:~w~n",[L3]),
    %%lists_filter(Cur,All2,[])。
    Pid = 自己()、
    Ref1=make_ref(),
    Ref2=make_ref(),
    erlang:spawn(?MODULE,sieve,[{Pid,Ref1},L1,Last]),
    erlang:spawn(?MODULE,sieve,[{Pid,Ref2},L3,Last]),
    Res1=受信
         {Ref1,R1} ->
         {1,R1};
         {Ref2,R1} ->
         {2,R1}
     終わり、
    Res2= 受信
          {Ref1,R2} ->
          {1,R2};
          {Ref2,R2} ->
          {2,R2}
      終わり、
    apnd(フィルター、Res1、Res2)。


filter([H|T],Last) H の場合
    [H|filters(T,Last)];
フィルタ([H|_],_) ->
    [H];
フィルター(_,_) ->
    []。


apnd(フィルタ,{1,N1},{2,N2}) ->
    リスト：追加（N1、減算（N2、フィルター））;
apnd(フィルタ,{2,N2},{1,N1}) ->
    リスト：追加（N1、減算（N2、フィルター））。



減算([H|L],[H|T]) ->
    減算 (L、T);
減算(L=[A|_],[B|_]) when A > B ->
    L;
減算(L,[_|T]) ->
    減算 (L、T);
減算(L,[]) ->
    L.

score 1 · Accepted Answer

Erlang で素数を見つけるための 4 つの異なる実装 (そのうちの 2 つは「実際の」ふるい) とパフォーマンス測定結果については、こちらを参照してください。

http://caylespandon.blogspot.com/2009/01/in-euler-problem-10-we-are-asked-to.html

score 1 · Accepted Answer

これらを詳しく調べたわけではありませんが、以下の実装 (Project Euler の課題のために書いたもの) をテストしましたが、上記の 2 つの実装よりも桁違いに高速です。いくつかのカスタム関数を削除し、代わりにリスト (同じことを行う関数) を探すまでは、非常に遅かったです。必要なことのライブラリ実装があるかどうかを常に確認するためのレッスンを学ぶことは良いことです - 通常はより速くなります! これは、2.8 GHz の iMac で 3.6 秒で 200 万までの素数の合計を計算します...

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Sum of all primes below Max. Will use sieve of Eratosthenes 
sum_primes(Max) ->
    LastCheck = round(math:sqrt(Max)),
    All = lists:seq(3, Max, 2), %note are creating odd-only array
    Primes = sieve(All, Max, LastCheck),
    %io:format("Primes: ~p~n", [Primes]),
    lists:sum(Primes) + 2. %adding back the number 2 to the list

%sieve of Eratosthenes
sieve(All, Max, LastCheck) ->
    sieve([], All, Max, LastCheck).

sieve(Primes, All, Max, LastCheck) ->
    %swap the first element of All onto Primes 
    [Cur|All2] = All,
    Primes2 = [Cur|Primes],
    case Cur > LastCheck of 
        true ->
            lists:append(Primes2, All2); %all known primes and all remaining from list (not sieved) are prime
        false -> 
            All3 = lists:filter(fun(X) -> X rem Cur =/= 0 end, All2),
            sieve(Primes2, All3, Max, LastCheck)

    end.

score 0 · Accepted Answer

これが私のエラトフェン実装C&Cのふるいです:

    -module(sieve).
    -export([find/2,mark/2,primes/1]).

    primes(N) -> [2|lists:reverse(primes(lists:seq(2,N),2,[]))].

    primes(_,0,[_|T]) -> T;
    primes(L,P,Primes) -> NewList = mark(L,P),
        NewP = find(NewList,P),
        primes(NewList,NewP,[NewP|Primes]).

    find([],_) -> 0;
    find([H|_],P) when H > P -> H;
    find([_|T],P) -> find(T,P). 


    mark(L,P) -> lists:reverse(mark(L,P,2,[])).

    mark([],_,_,NewList) -> NewList;
    mark([_|T],P,Counter,NewList) when Counter rem P =:= 0 -> mark(T,P,Counter+1,[P|NewList]);
    mark([H|T],P,Counter,NewList) -> mark(T,P,Counter+1,[H|NewList]).

score -1 · Accepted Answer

これまでの私の最速のコード（Andreaのものよりも速い）は配列を使用することです：

-module(seed4).
-export([get/1]).

get(N) -> WorkList = array:new([{size, N}, {default, empty}]),
          get(2, N, WorkList, []).

get(thats_the_end, _N, _WorkList, ResultList) -> lists:reverse(ResultList);
get(CurrentPrime, N, WorkList, ResultList) -> ModWorkList = markAsPrime(CurrentPrime, N, WorkList),
                                              NextPrime = findNextPrime(CurrentPrime + 1, N, WorkList),
                                              get(NextPrime, N, ModWorkList, [CurrentPrime|ResultList]).


markAsPrime(CurrentPrime, N, WorkList) when CurrentPrime =< N -> WorkListMod = replace(CurrentPrime, WorkList, prime),
                                                                 markAllMultiples(CurrentPrime, N, 2*CurrentPrime, WorkListMod).

markAllMultiples(_ThePrime, N, TheCurentMark, WorkList) when TheCurentMark > N -> WorkList;
markAllMultiples(ThePrime, N, TheCurrentMark, WorkList) -> WorkListMod = replace(TheCurrentMark, WorkList, marked),
                                                           markAllMultiples(ThePrime, N, TheCurrentMark + ThePrime, WorkListMod).

findNextPrime(Iterator, N, _WorkList) when Iterator > N -> thats_the_end;
findNextPrime(Iterator, N, WorkList) -> I = array:get(Iterator - 1, WorkList),
                                        if
                                          I =:= empty -> Iterator;
                                          true -> findNextPrime(Iterator + 1, N, WorkList)
                                        end.

replace(N, L, New) -> array:set(N - 1, New, L).

erlang - アーランのエラトステネスのふるい

12 に答える 12

Related

Reference