Сито Эратосфена в Эрланге

Question

Я изучаю Эрланг. В качестве упражнения я подобрал алгоритм генерации простых чисел Sieve of Eratosthenes. Вот мой код:

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

Этот код фактически работает :). Проблема в том, что у меня такое ощущение, что это не самая лучшая реализация.

Мой вопрос, что было бы «erlangish» способ реализации «Решето Эратосфена»

EDIT: Хорошо, решение Andreas очень хорошо, но это очень медленный процесс. Любые идеи, как улучшить это?

Answer 1

Вот простой (но не очень быстро) реализация решето:

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

Answer 2

Я подошел к проблеме, используя параллельную обработку.

Source

Answer 3

мой быстрый код до сих пор (быстрее, чем Андреа) находится с помощью массива:

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

Answer 4

Я не изучил их подробно, но я протестировал свою реализацию ниже (что я написал для Project Euler challenge), и это на порядок быстрее, чем предыдущие два Реализации. Это было мучительно медленным, пока я не устранил некоторые пользовательские функции и вместо этого искал списки: функции, которые бы сделали то же самое. Приятно выучить урок, чтобы всегда видеть, есть ли в библиотеке что-то, что вам нужно сделать - это, как правило, быстрее! Это вычисляет сумму простых чисел до 2 миллионов в 3,6 секунды на частоте 2,8 ГГц ИМАК ...

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

Answer 5

Я вроде как эту тему, простых чисел, поэтому я начал изменять код BarryE немного, и я чтобы сделать его примерно на 70% быстрее, выполнив мою собственную функцию lists_filter и позволив использовать оба моих процессора. Я также упростил обмен между двумя версиями. Пробный запуск показывает:

 
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. 

Answer 6

Мой предыдущий пост не получил отформатирован правильно. Вот репозиция кода. Извините за спам ...

 

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

Answer 7

вы могли бы показать ваш босс это: http://www.sics.se/~joe/apachevsyaws.html. И некоторые другие (классические?) Аргументы erlang:

-непрерывная работа, новый код может быть загружен на лету.

-легко отлаживать, больше нет отвалов для анализа.

-легко использовать многоядерные/процессоры

-Easy, чтобы использовать кластеры, может быть?

-who хочет иметь дело с указателями и прочее? Разве это не 21 век?;)

Некоторые пифаллы: - может быть легко и быстро написать что-нибудь, но производительность может сосать. Если я хочу сделать что-то быстро, я обычно заканчиваю написанием 2-4 различных версий той же функции . И часто вам нужно заглядывать в глаза ястребов, которые могут быть , немного отличающимися от того, что используется.

• поиск в списках> около 1000 элементов медленно, попробуйте использовать таблицы ets.

• строка «abc» занимает намного больше места, чем 3 байта. Поэтому попробуйте использовать двоичные файлы (это боль).

В целом, я думаю, что проблема с производительностью - это что-то, что нужно помнить во время написания чего-то в erlang. У парней Эрланга это нужно, и я думаю, что они это сделают.

Answer 8

Посмотри здесь, чтобы найти 4 различные реализации для нахождения простых чисел в Erlang (два из которых является «настоящим» Сито) и для результатов измерения производительности:

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

Answer 9

Вот мои реализация сита, которая использует списки и пытается быть рекурсивной. Как инвертировать список в конце, так что простые числа сортируются:

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,8 мс для расчета простых чисел до 2 мил на мой 2GHz макинтош.

Answer 10

Простой, реализует именно алгоритм и не использует библиотечные функции (только соответствие шаблонов и понимание списка). Не очень мощный, действительно. Я старался сделать это как можно проще.

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

Answer 11

Вот мой решето реализации 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]). 

Answer 12

Вот мой пример

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

:-)