Tamiz de Eratóstenes en Erlang

sieve-of-eratosthenes

Question

Estoy en el proceso de aprender Erlang. Como ejercicio, elegí el algoritmo Sieve of Eratosthenes para generar números primos. Aquí está mi código:

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

Este código realmente funciona :). El problema es que tengo la sensación de que no es la mejor implementación posible.

Mi pregunta es cuál sería la forma "erlangish" de implementar el "Tamiz de Eratóstenes"

EDITAR: OK, la solución de Andreas es muy buena, pero lenta. ¿Alguna idea de cómo mejorar eso?

Answer 1

No los he estudiado en detalle, pero he probado mi implementación a continuación (que escribí para un desafío del Proyecto Euler) y es mucho más rápida que las dos implementaciones anteriores. Fue insoportablemente lento hasta que eliminé algunas funciones personalizadas y en su lugar busqué listas: funciones que harían lo mismo. Es bueno aprender la lección para ver siempre si hay una implementación de la biblioteca de algo que debe hacer, ¡generalmente será más rápido! Esto calcula la suma de primos de hasta 2 millones en 3,6 segundos en un iMac de 2,8 GHz ...

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

Abordé el problema mediante el uso de procesamiento simultáneo.

Fuente

Answer 3

Aquí hay una implementación de criba simple (pero no terriblemente rápida):

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

Me gusta este tema, primos que sí, así que empecé a modificar el código de BarryE un poco y logré hacerlo un 70% más rápido al hacer mi propia función lists_filter y hacer posible el uso de mis dos CPUs. También hice que sea fácil cambiar entre dos versiones. Una ejecución de prueba muestra:

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

Código:

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

Mi publicación anterior no se formateó correctamente. Aquí hay un reenvío del código. Perdón por enviar spam ...

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

usted podría mostrarle a su jefe esto: http://www.sics.se/~joe/apachevsyaws.html . Y algunos otros (clásicos?) Argumentos de Erlang son:

-operación ininterrumpida, el nuevo código se puede cargar sobre la marcha.

-fácil de depurar, no más volcados de núcleo para analizar.

-fácil de utilizar multi core / CPU

-Fácil de utilizar clusters tal vez?

¿Quién quiere lidiar con punteros y esas cosas? ¿No es este el siglo 21? ;)

Algunos pifalls: puede parecer fácil y rápido escribir algo, pero el rendimiento puede apestar. Si quiero hacer algo rápido, generalmente termino escribiendo 2-4 versiones diferentes de la misma función. Y a menudo necesitas tomar un enfoque de ojo de halcón a los problemas que podrían ser un poco diferentes de lo que se usa también.

• buscar cosas en las listas> alrededor de 1000 elementos es lento, intente usar las tablas ets.

• la cadena "abc" ocupa mucho más espacio que 3 bytes. Intenta usar binarios, (que es un dolor).

En general, creo que el problema de rendimiento es algo a tener en cuenta en todo momento al escribir algo en erlang. Los tipos Erlang necesitan resolver eso, y creo que lo harán.

Answer 7

Eche un vistazo aquí para encontrar 4 implementaciones diferentes para encontrar números primos en Erlang (dos de los cuales son tamices "reales") y para resultados de medición de rendimiento:

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

Answer 8

Lo suficientemente simple, implementa exactamente el algoritmo y no utiliza funciones de biblioteca (solo coincidencias de patrones y comprensión de listas). No es muy poderoso, de hecho. Solo intenté hacerlo lo más simple posible.

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

Aquí está mi implementación de tamiz que usa listas de comprensión e intenta ser recursivo de cola. Inverso la lista al final para que los primos estén ordenados:

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

Toma aproximadamente 2.8 ms para calcular números primos hasta 2 mil en mi mac 2ghz.

Answer 10

Aquí está mi criba de la implementación de eratophenes C & C por favor:

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

Aquí está mi muestra

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

:-)

Answer 12

mi código más rápido hasta ahora (más rápido que el de Andrea) es con el uso de matriz:

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