سؤال
أواجه المشكلات على موقع projecteuler.net لأتعلم كيفية البرمجة بلغة Erlang، وأواجه صعوبة كبيرة في إنشاء مولد أولي يمكنه إنشاء جميع الأعداد الأولية التي يقل عددها عن 2 مليون، في أقل من دقيقة.باستخدام الأسلوب المتسلسل، كتبت بالفعل ثلاثة أنواع من المولدات، بما في ذلك غربال إراتوستينس، ولم يكن أي منها يعمل بشكل جيد بما فيه الكفاية.
اعتقدت أن الغربال المتزامن سيعمل بشكل رائع، ولكنني أتلقى رسائل سيئة، ولست متأكدًا من السبب.هل هناك أي اقتراحات حول سبب المشكلة، أو كيفية ترميزها بشكل صحيح؟
هذا هو الكود الخاص بي، الأقسام التي تم التعليق عليها هي المكان الذي حاولت فيه جعل الأشياء متزامنة:
-module(primeserver). -compile(export_all). start() -> register(primes, spawn(fun() -> loop() end)). is_prime(N) -> rpc({is_prime,N}). rpc(Request) -> primes ! {self(), Request}, receive {primes, Response} -> Response end. loop() -> receive {From, {is_prime, N}} -> if N From ! {primes, false}; N =:= 2 -> From ! {primes, true}; N rem 2 =:= 0 -> From ! {primes, false}; true -> Values = is_not_prime(N), Val = not(lists:member(true, Values)), From ! {primes, Val} end, loop() end. for(N,N,_,F) -> [F(N)]; for(I,N,S,F) when I + S [F(I)|for(I+S, N, S, F)]; for(I,N,S,F) when I + S =:= N -> [F(I)|for(I+S, N, S, F)]; for(I,N,S,F) when I + S > N -> [F(I)]. get_list(I, Limit) -> if I [I*A || A [] end. is_not_prime(N) -> for(3, N, 2, fun(I) -> List = get_list(I,trunc(N/I)), lists:member(N,lists:flatten(List)) end ). %%L = for(1,N, fun() -> spawn(fun(I) -> wait(I,N) end) end), %%SeedList = [A || A %% lists:foreach(fun(X) -> %% Pid ! {in_list, X} %% end, SeedList) %% end, L). %%wait(I,N) -> %% List = [I*A || A lists:member(X,List) %% end.
المحلول
الخطأ "badarity" يعني أنك تحاول تسمية "fun" بعدد خاطئ من الوسائط.في هذه الحالة...
%%L = for(1,N, fun() -> Spawn(fun(I) -> wait(I,N) end) end),
تتوقع الدالة for/3 متعة arity 1، وتتوقع وظيفة spawn/1 متعة arity 0.جرب هذا بدلاً من ذلك:
L = for(1, N, fun(I) -> spawn(fun() -> wait(I, N) end) end),
ترث المتعة التي تم تمريرها للنشر الأجزاء المطلوبة من بيئتها (أي أنا)، لذا ليست هناك حاجة لتمريرها بشكل صريح.
على الرغم من أن حساب الأعداد الأولية يعد أمرًا ممتعًا دائمًا، يرجى الأخذ في الاعتبار أن هذه ليست مشكلة من النوع الذي صمم Erlang لحلها.تم تصميم Erlang للتزامن الضخم على غرار الممثل.من المرجح أن يكون أداؤها سيئًا إلى حد ما في جميع أمثلة الحساب المتوازي للبيانات.في كثير من الحالات، حل تسلسلي في ML، على سبيل المثال سيكون سريعًا جدًا لدرجة أن أي عدد من النوى لن يكون كافيًا لـ Erlang للحاق به، وعلى سبيل المثال. F# والمكتبة الموازية للمهام .NET سيكون بالتأكيد وسيلة أفضل بكثير لمثل هذه الأنواع من العمليات.
نصائح أخرى
لقد كتبت منخلًا رئيسيًا متزامنًا لإراتوستينسك باستخدام Go والقنوات.
هنا هو الرمز: http://github.com/aht/gosieve
أنا كتبت عن ذلك هنا: http://blog.onideas.ws/eratosthenes.go
يمكن للبرنامج غربلة أول مليون عدد أولي (جميع الأعداد الأولية تصل إلى 15,485,863) في حوالي 10 ثوانٍ.الغربال متزامن، لكن الخوارزمية متزامنة بشكل أساسي:هناك عدد كبير جدًا من نقاط المزامنة المطلوبة بين goroutines ("الممثلين" - إذا أردت) وبالتالي لا يمكنهم التجول بحرية بالتوازي.
البديل الآخر الذي يجب مراعاته هو استخدام الجيل الأولي الاحتمالي.يوجد مثال على ذلك في كتاب جو ("الخادم الرئيسي") الذي يستخدم ميلر رابين على ما أعتقد...
يمكنك العثور على أربعة تطبيقات مختلفة لـ Erlang للعثور على الأعداد الأولية (اثنتان منها تعتمدان على غربال إراتوستينس). هنا.يحتوي هذا الرابط أيضًا على رسوم بيانية تقارن أداء الحلول الأربعة.
إن غربال إراتوستينس سهل التنفيذ إلى حد ما، ولكنه - كما اكتشفت - ليس الأكثر كفاءة.هل قمت بتجربة غربال أتكين؟
خوارزمية الأعداد الأولية المتوازية: http://www.cs.cmu.edu/~scandal/cacm/node8.html
اثنين من مولدات إرلانج الأولية السريعة ذات العملية الواحدة؛يقوم sprimes بإنشاء جميع الأعداد الأولية التي يقل طولها عن 2 متر في 2.7 ثانية تقريبًا، وfprimes حوالي 3 ثوانٍ على جهاز الكمبيوتر الخاص بي (Macbook المزود بمعالج Core 2 Duo بسرعة 2.4 جيجا هرتز).كلاهما يعتمد على غربال إراتوستينس، ولكن نظرًا لأن إرلانج يعمل بشكل أفضل مع القوائم، بدلاً من المصفوفات، فإن كلاهما يحتفظ بقائمة من الأعداد الأولية غير المحذوفة، ويتحقق من قابلية القسمة على الرأس الحالي ويحتفظ بمجمع من الأعداد الأولية التي تم التحقق منها.يقوم كلاهما أيضًا بتنفيذ عجلة رئيسية لإجراء التخفيض الأولي للقائمة.
-module(primes).
-export([sprimes/1, wheel/3, fprimes/1, filter/2]).
sieve([H|T], M) when H=< M -> [H|sieve([X || X<- T, X rem H /= 0], M)];
sieve(L, _) -> L.
sprimes(N) -> [2,3,5,7|sieve(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), math:sqrt(N))].
wheel([X|Xs], _Js, M) when X > M ->
lists:reverse(Xs);
wheel([X|Xs], [J|Js], M) ->
wheel([X+J,X|Xs], lazy:next(Js), M);
wheel(S, Js, M) ->
wheel([S], lazy:lazy(Js), M).
fprimes(N) ->
fprimes(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), [7,5,3,2], N).
fprimes([H|T], A, Max) when H*H =< Max ->
fprimes(filter(H, T), [H|A], Max);
fprimes(L, A, _Max) -> lists:append(lists:reverse(A), L).
filter(N, L) ->
filter(N, N*N, L, []).
filter(N, N2, [X|Xs], A) when X < N2 ->
filter(N, N2, Xs, [X|A]);
filter(N, _N2, L, A) ->
filter(N, L, A).
filter(N, [X|Xs], A) when X rem N /= 0 ->
filter(N, Xs, [X|A]);
filter(N, [_X|Xs], A) ->
filter(N, Xs, A);
filter(_N, [], A) ->
lists:reverse(A).
Lazy:lazy/1 و Lazy:next/1 يشيران إلى تطبيق بسيط للقوائم اللانهائية الكسولة الزائفة:
lazy(L) ->
repeat(L).
repeat(L) -> L++[fun() -> L end].
next([F]) -> F()++[F];
next(L) -> L.
لا يعد التوليد الأولي بواسطة المناخل مكانًا رائعًا للتزامن (ولكن يمكن استخدام التوازي في التحقق من قابلية القسمة، على الرغم من أن العملية ليست معقدة بما يكفي لتبرير الحمل الإضافي لجميع المرشحات المتوازية التي كتبتها حتى الآن).
`
مشاكل مشروع أويلر (أقول أن معظم المشاكل الخمسين الأولى إن لم يكن أكثر) تتعلق في الغالب بالقوة الغاشمة مع لمسة من البراعة في اختيار حدودك.
تذكر أن تختبر ما إذا كان N أوليًا (بالقوة الغاشمة)، ما عليك سوى معرفة ما إذا كان قابلاً للقسمة على أي عدد أولي حتى الطابق (sqrt(N)) + 1، وليس N/2.
حظ سعيد
أنا أحب مشروع أويلر.
فيما يتعلق بموضوع المولدات الأولية، فأنا من أشد المعجبين بغربال إراتوستينس.
لأغراض الأرقام الأقل من 2,000,000، يمكنك تجربة تنفيذ عملية فحص isPrime البسيطة.لا أعرف كيف ستفعل ذلك بلغة إرلانج، لكن المنطق بسيط.
For Each NUMBER in LIST_OF_PRIMES
If TEST_VALUE % NUMBER == 0
Then FALSE
END
TRUE
if isPrime == TRUE add TEST_VALUE to your LIST_OF_PRIMES
iterate starting at 14 or so with a preset list of your beginning primes.
قام c# بتشغيل قائمة مثل هذه بمبلغ 2,000,000 أقل بكثير من علامة الدقيقة الواحدة
يحرر: في ملاحظة جانبية، يمكن تنفيذ غربال إراتوستينس بسهولة وتشغيله بسرعة، ولكنه يصبح غير عملي عندما تبدأ في الدخول في قوائم ضخمة.أبسط تنفيذ، باستخدام مصفوفة منطقية وقيم int، يعمل بسرعة كبيرة.تكمن المشكلة في أنك تبدأ في مواجهة حدود حجم القيمة الخاصة بك بالإضافة إلى طول المصفوفة الخاصة بك.- يساعد التبديل إلى تنفيذ سلسلة أو مصفوفة ثنائية، ولكن لا يزال أمامك التحدي المتمثل في التكرار عبر قائمتك بقيم كبيرة.
هنا نسخة vb
'Sieve of Eratosthenes
'http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
'1. Create a contiguous list of numbers from two to some highest number n.
'2. Strike out from the list all multiples of two (4, 6, 8 etc.).
'3. The list's next number that has not been struck out is a prime number.
'4. Strike out from the list all multiples of the number you identified in the previous step.
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
'6. All the remaining numbers in the list are prime.
Private Function Sieve_of_Eratosthenes(ByVal MaxNum As Integer) As List(Of Integer)
'tested to MaxNum = 10,000,000 - on 1.8Ghz Laptop it took 1.4 seconds
Dim thePrimes As New List(Of Integer)
Dim toNum As Integer = MaxNum, stpw As New Stopwatch
If toNum > 1 Then 'the first prime is 2
stpw.Start()
thePrimes.Capacity = toNum 'size the list
Dim idx As Integer
Dim stopAT As Integer = CInt(Math.Sqrt(toNum) + 1)
'1. Create a contiguous list of numbers from two to some highest number n.
'2. Strike out from the list all multiples of 2, 3, 5.
For idx = 0 To toNum
If idx > 5 Then
If idx Mod 2 <> 0 _
AndAlso idx Mod 3 <> 0 _
AndAlso idx Mod 5 <> 0 Then thePrimes.Add(idx) Else thePrimes.Add(-1)
Else
thePrimes.Add(idx)
End If
Next
'mark 0,1 and 4 as non-prime
thePrimes(0) = -1
thePrimes(1) = -1
thePrimes(4) = -1
Dim aPrime, startAT As Integer
idx = 7 'starting at 7 check for primes and multiples
Do
'3. The list's next number that has not been struck out is a prime number.
'4. Strike out from the list all multiples of the number you identified in the previous step.
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
If thePrimes(idx) <> -1 Then ' if equal to -1 the number is not a prime
'not equal to -1 the number is a prime
aPrime = thePrimes(idx)
'get rid of multiples
startAT = aPrime * aPrime
For mltpl As Integer = startAT To thePrimes.Count - 1 Step aPrime
If thePrimes(mltpl) <> -1 Then thePrimes(mltpl) = -1
Next
End If
idx += 2 'increment index
Loop While idx < stopAT
'6. All the remaining numbers in the list are prime.
thePrimes = thePrimes.FindAll(Function(i As Integer) i <> -1)
stpw.Stop()
Debug.WriteLine(stpw.ElapsedMilliseconds)
End If
Return thePrimes
End Function