Tamiz de Eratóstenes en Erlang [cerrado]
https://stackoverflow.com/questions/146622
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy en el proceso de aprender Erlang. Como ejercicio, seleccioné el algoritmo Tamiz de Eratóstenes 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 el " erlangish " forma de implementar el " Tamiz de Eratóstenes "
EDITAR: OK, la solución de Andreas es muy buena pero es lenta. ¿Alguna idea de cómo mejorar eso?
Solución
Aquí hay una implementación de tamiz 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)).
Otros consejos
Aquí está la implementación de mi tamiz que usa listas de comprensión e intenta ser recursiva. Invierto 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 de hasta 2 mil en mi 2ghz mac.
Abordé el problema utilizando un procesamiento simultáneo.
Mi publicación anterior no se formateó correctamente. Aquí hay un repost del código. Perdón por el spamming ...
-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.
No he estudiado esto 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ápido que las dos implementaciones anteriores. Fue insoportablemente lento hasta que eliminé algunas funciones personalizadas y, en cambio, 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 deba hacer. ¡Por lo general, será más rápido! Esto calcula la suma de números primos hasta 2 millones en 3.6 segundos en un iMac de 2.8GHz ...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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.
Me gusta este tema, es decir, primos, así que comencé a modificar un poco el código de BarryE y logré hacerlo un 70% más rápido al hacer mi propia función lists_filter e hice posible utilizar mis dos CPU. También facilité el intercambio entre dos versiones. Una prueba de ejecución 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.
podría mostrarle a su jefe esto: http://www.sics.se/~ joe / apachevsyaws.html . Y algunos otros argumentos (clásicos?) De erlang son:
- operación no detenida, el nuevo código se puede cargar sobre la marcha.
: fácil de depurar, no hay más volcados de datos para analizar.
-fácil de utilizar multi core / CPU
: ¿es fácil utilizar clústeres?
-quien quiere lidiar con punteros y esas cosas? ¿No es este el siglo 21? ;)
Algunas trampas: - Puede parecer fácil y rápido escribir algo, pero el rendimiento puede apestar. Si yo Quiero hacer algo rápido, normalmente termino escribiendo 2-4 versiones diferentes de la misma. función. Y a menudo es necesario tomar un enfoque de ojo de halcón a problemas que podrían ser una un poco diferente de lo que se usa también.
-
buscando cosas en listas > alrededor de 1000 elementos es lento, intente usar ets tablas.
-
la cadena " abc " ocupa mucho más espacio que 3 bytes. Así que trate de usar binarios, (que es un dolor).
En general, creo que el problema de rendimiento es algo que se debe tener en cuenta en todo momento cuando se escribe algo en erlang. Los tipos de Erlang deben resolverlo, y creo que lo harán.
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 obtener resultados de medición de rendimiento:
http: / /caylespandon.blogspot.com/2009/01/in-euler-problem-10-we-are-asked-to.html
Bastante simple, implementa exactamente el algoritmo y no utiliza funciones de biblioteca (solo coincidencia de patrones y comprensión de listas). No muy poderoso, por cierto. 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)].
Aquí está mi tamiz de implementación de eratóstenes C & amp; 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]).
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]).
:-)
mi código más rápido hasta ahora (más rápido que el de Andrea) es con el uso de 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).
