غربال إراتوستينس في إرلانج [مغلق]
https://stackoverflow.com/questions/146622
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا بصدد تعلم 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]).
هذا الرمز يعمل بالفعل :) .المشكلة هي أنني أشعر بأن هذا ليس أفضل تنفيذ ممكن.
سؤالي هو ما هي الطريقة "الإيرلندية" لتنفيذ "غربال إراتوستينس"؟
يحرر:حسنًا، حل أندرياس جيد جدًا ولكنه بطيء.أي أفكار حول كيفية تحسين ذلك؟
المحلول
فيما يلي تنفيذ غربال بسيط (ولكن ليس سريعًا جدًا):
-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
يستغرق حوالي 2.8 مللي ثانية لحساب أعداد أولية تصل إلى 2 مليون على جهاز Mac بسرعة 2 جيجا هرتز.
لقد تعاملت مع المشكلة باستخدام المعالجة المتزامنة.
لم يتم تنسيق مشاركتي السابقة بشكل صحيح.هنا إعادة نشر للكود.آسف على البريد العشوائي...
-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.
لم أدرسها بالتفصيل، لكنني اختبرت تطبيقي أدناه (الذي كتبته لتحدي مشروع أويلر) وهو أسرع من حيث الحجم من التطبيقين المذكورين أعلاه.لقد كان الأمر بطيئًا للغاية حتى قمت بإزالة بعض الوظائف المخصصة وبحثت بدلاً من ذلك عن القوائم:الوظائف التي من شأنها أن تفعل الشيء نفسه.من الجيد أن تتعلم الدرس لترى دائمًا ما إذا كان هناك تطبيق مكتبة لشيء تحتاج إلى القيام به - وعادةً ما يكون ذلك أسرع!يقوم هذا بحساب مجموع الأعداد الأولية حتى 2 مليون في 3.6 ثانية على جهاز iMac بسرعة 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.
أنا أحب هذا الموضوع نوعًا ما، أي الأعداد الأولية، لذلك بدأت في تعديل كود 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.
يمكنك أن تظهر لرئيسك هذا: http://www.sics.se/~joe/apachevsyaws.html.وبعض وسيطات erlang الأخرى (الكلاسيكية؟) هي:
-عملية بدون توقف، يمكن تحميل التعليمات البرمجية الجديدة بسرعة.
- سهل التصحيح، لا مزيد من عمليات التفريغ الأساسية للتحليل.
- سهولة استخدام وحدات المعالجة المركزية/النواة المتعددة
- من السهل استخدام المجموعات ربما؟
-من يريد التعامل مع المؤشرات والأشياء؟أليس هذا هو القرن الحادي والعشرين؟;)
بعض المفاسد:- قد يبدو الأمر سهلاً وسريعًا لكتابة شيء ما، ولكن الأداء قد يكون سيئًا.إذا أردت أن أجعل شيئًا سريعًا ، فعادة ما ينتهي بي الأمر إلى كتابة 2-4 إصدارات مختلفة من نفس الوظيفة.وغالبًا ما تحتاج إلى أخذ عين صقر للمشاكل التي قد تكون مختلفة قليلاً عما يستخدمه الشخص أيضًا.
البحث عن الأشياء في القوائم > حوالي 1000 عنصر أمر بطيء، حاول استخدام جداول ets.
تأخذ السلسلة "abc" مساحة أكبر بكثير من 3 بايت.لذا حاول استخدام الثنائيات (وهو أمر مؤلم).
بشكل عام، أعتقد أن مشكلة الأداء هي أمر يجب أخذه في الاعتبار في جميع الأوقات عند كتابة شيء ما باللغة إيرلانج.يحتاج رجال إيرلانج إلى حل ذلك، وأعتقد أنهم سيفعلون ذلك.
ألقِ نظرة هنا للعثور على 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)].
إليكم غربال تنفيذ الإيراتوفين 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]).
هنا عينة بلدي
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]).
:-)
أسرع كود لدي حتى الآن (أسرع من كود أندريا) هو باستخدام المصفوفة:
-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).
