Tamis d'Eratosthenes à Erlang [fermé]
https://stackoverflow.com/questions/146622
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis en train d'apprendre Erlang. À titre d’exercice, j’ai retenu l’algorithme de Sieve of Eratosthenes pour générer des nombres premiers. Voici mon code:
-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]).
Ce code fonctionne réellement :). Le problème, c’est que j’ai le sentiment que ce n’est pas la meilleure mise en oeuvre possible.
Ma question est de savoir quel serait le "erlangish" manière de mettre en oeuvre le "tamis d'Eratosthène"
EDIT: OK, la solution Andreas est très bonne mais lente. Des idées pour améliorer ça?
La solution
Voici une implémentation de tamis simple (mais pas très rapide):
-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)).
Autres conseils
Voici mon implémentation de tamis qui utilise des compréhensions de liste et tente d’être récursive. J'inverse la liste à la fin pour que les nombres premiers soient triés:
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
Prend environ 2,8 ms pour calculer les nombres premiers allant jusqu'à 2 mil sur mon mac 2ghz.
J'ai abordé le problème en utilisant un traitement simultané.
Mon précédent message n'a pas été correctement formaté. Voici un repost du code. Désolé pour le 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.
Je n’ai pas étudié cela en détail, mais j’ai testé mon implémentation ci-dessous (celle que j’ai écrite pour un défi Project Euler) et c’est beaucoup plus rapide que les deux implémentations ci-dessus. C'était extrêmement lent jusqu'à ce que j'élimine certaines fonctions personnalisées et que je cherche plutôt des listes: des fonctions qui feraient la même chose. Il est bon d’apprendre la leçon pour toujours savoir s’il ya une implémentation dans la bibliothèque de quelque chose que vous devez faire - ce sera généralement plus rapide! Ceci calcule la somme de nombres premiers allant jusqu’à 2 millions en 3,6 secondes sur un iMac à 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.
J'aime beaucoup ce sujet, c'est-à-dire les nombres premiers. J'ai donc commencé à modifier un peu le code de BarryE et j'ai réussi à le rendre environ 70% plus rapide en créant ma propre fonction lists_filter et en permettant d'utiliser mes deux processeurs. J'ai également rendu facile à permuter entre deux versions. Un test montre:
61> timer:tc(test,sum_primes,[2000000]).
{2458537,142913970581}
Code:
-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.
vous pouvez montrer à votre patron ceci: http://www.sics.se/~ joe / apachevsyaws.html . Et quelques autres arguments (classiques?) Erlang sont:
-non-stop opération, nouveau code peut être chargé à la volée.
-facile à déboguer, plus de dumps de noyau à analyser.
-facile à utiliser des processeurs multicœurs /
-facile d’utiliser des grappes peut-être?
-qui veut gérer les pointeurs? N'est-ce pas le 21ème siècle? ;)
Quelques pifalls: - il peut sembler facile et rapide d’écrire quelque chose, mais la performance peut être nulle. Si je veux faire quelque chose de rapide, je finis habituellement par écrire 2-4 versions différentes de la même une fonction. Et souvent, vous devez adopter une approche oculaire de faucon qui pourrait être un problème. un peu différent de ce que l’on utilise aussi.
-
recherche d'éléments dans les listes > environ 1000 éléments est lent, essayez d’utiliser des tables ets.
-
la chaîne " abc " prend beaucoup plus d'espace que 3 octets. Essayez donc d’utiliser des binaires (ce qui est pénible).
Dans l’ensemble, j’estime qu’il est important de garder à l’esprit le problème des performances lors de l’écriture en erlang. Les gars d'Erlang doivent résoudre ce problème et je pense qu'ils le feront.
Regardez ici pour trouver 4 implémentations différentes pour trouver des nombres premiers dans Erlang (dont deux sont des tamis "réels") et pour obtenir des résultats de mesure du rendement:
http: / /caylespandon.blogspot.com/2009/01/in-euler-problem-10-we-are-asked-to.html
Assez simple, implémente exactement l'algorithme et n'utilise aucune fonction de bibliothèque (uniquement la recherche de modèle et la compréhension de liste). Pas très puissant, en effet. J'ai seulement essayé de le rendre aussi simple que possible.
-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)].
Voici mon tamis de mise en oeuvre des ératosthènes C & amp; C s'il vous plaît:
-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]).
Voici mon échantillon
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]).
: -)
Mon code le plus rapide jusqu'à présent (plus rapide que celui d'Andrea) est d'utiliser 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).
