Erlang의 Eratosthenes의 체 [폐쇄

StackOverflow https://stackoverflow.com/questions/146622

  •  02-07-2019
  •  | 
  •  

문제

나는 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]).

이 코드는 실제로 작동합니다 :). 문제는 그것이 가능한 최선의 구현이 아니라는 느낌을 가지고 있다는 것입니다.

내 질문은 "Eratosthenes의 체"를 구현하는 "erlangish"방법이 무엇인지입니다.

편집 : OK, Andreas 솔루션은 매우 좋지만 느립니다. 그것을 개선하는 방법이 있습니까?

도움이 되었습니까?

해결책

간단한 (그러나 매우 빠르지는 않지만) 체 구현은 다음과 같습니다.

-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)).

다른 팁

다음은 목록 이해력을 사용하고 꼬리 재귀를 시도하는 내 체시 구현입니다. 끝에 목록을 뒤집어 프라임이 정렬됩니다.

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

2GHz Mac에서 최대 2 mil의 프라임을 계산하는 데 약 2.8ms가 걸립니다.

동시 처리를 사용하여 문제에 접근했습니다.

원천

이전 게시물이 제대로 형식화되지 않았습니다. 다음은 코드의 재 게시입니다. 스팸에 대해 죄송합니다 ...


-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.

나는 이것을 자세히 연구하지 않았지만 아래 구현을 테스트했으며 (프로젝트 Euler Challenge를 위해 쓴) 위의 두 구현보다 훨씬 빠른 순서입니다. 몇 가지 사용자 정의 기능을 제거하고 대신 목록을 찾을 때까지는 극도로 느 렸습니다. 해야 할 일에 대한 라이브러리 구현이 있는지 항상 확인하는 것이 교훈을 배우는 것이 좋습니다. 일반적으로 더 빠릅니다! 이것은 2.8GHz imac에서 3.6 초 만에 최대 2 백만의 프라임의 합계를 계산합니다 ...

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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.

나는이 주제와 같은 종류, 즉 Primes, 즉 Barrye의 코드를 약간 수정하기 시작했고, 내 자신의 Lists_Filter 기능을 만들어 약 70% 더 빠르게 만들고 CPU를 모두 활용할 수있게했습니다. 또한 두 버전으로 쉽게 교체 할 수있었습니다. 테스트 런 쇼 :

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

암호:

-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),
    %%io:format("F:~p~n",[Filters]),
    L3 = lists:append(Filters,L2),
    %%io:format("L1:~w~n",[L1]),
    %%    io:format("L2:~w~n",[L3]),
    %%lists_filter(Cur,All2,[]).
    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.

당신은 당신의 상사를 보여줄 수 있습니다 : http://www.sics.se/~joe/apachevsyaws.html. 그리고 다른 (고전적인?) Erlang 주장은 다음과 같습니다.

-Nonstop 작동, 새 코드는 즉시로드 될 수 있습니다.

-디버그하기 쉬우 며, 더 이상 코어 덤프를 분석 할 수 없습니다.

-멀티 코어/CPU를 활용하는 것이 좋습니다

-클러스터를 사용하는 것이 아닐까요?

-누가 포인터와 물건을 다루고 싶습니까? 이것은 21 세기가 아닌가? ;)

일부 pifalls : - 무언가를 쓰는 것은 쉽고 빠르게 보일 수 있지만 성능은 빨라질 수 있습니다. 빨리 무언가를 만들고 싶다면 일반적으로 2-4 개의 다른 버전의 동일한 기능을 작성하게됩니다. 그리고 종종 당신은 종종 호크 아이를 aproach로 가져 가서 사용되는 것과 약간 다른 문제에 대해 aproach를 가져 가야합니다.

  • 목록에서 물건을 찾아보십시오> 약 1000 개의 요소가 느립니다. ETS 테이블을 사용해보십시오.

  • 문자열 "ABC"는 3 바이트보다 훨씬 더 많은 공간을 차지합니다. 따라서 바이너리를 사용하십시오 (고통).

대체로 나는 성능 문제가 Erlang에서 무언가를 쓸 때 항상 명심해야 할 것이라고 생각합니다. Erlang Dudes는 그 일을해야합니다. 그리고 나는 그들이 그렇게 할 것이라고 생각합니다.

Erlang에서 소수를 찾기위한 4 가지 구현 (2 개는 "실제"체계) 및 성능 측정 결과를 찾기 위해 4 가지 구현을 찾으십시오.

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

충분히 간단하고 알고리즘을 정확하게 구현하고 라이브러리 기능을 사용하지 않습니다 (패턴 일치 및 목록 이해 만). 참으로 강력하지 않습니다. 나는 가능한 한 간단하게 만들려고 노력했다.

-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)].

다음은 내 Eratophenes 구현 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]).

Here is my sample

S = lists:seq(2,100),
lists:foldl(fun(A,X) -> X--[A] end,S,[Y||X<-S,Y<-S,X<math:sqrt(Y)+1,Y rem X==0]).

:-)

my fastest code so far (faster than Andrea's) is with using array:

-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).
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top