مولد رئيس متزامن

Question

أواجه المشكلات على موقع 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.

Answer 1

الخطأ "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 سيكون بالتأكيد وسيلة أفضل بكثير لمثل هذه الأنواع من العمليات.

Answer 2

لقد كتبت منخلًا رئيسيًا متزامنًا لإراتوستينسك باستخدام Go والقنوات.

هنا هو الرمز: http://github.com/aht/gosieve

أنا كتبت عن ذلك هنا: http://blog.onideas.ws/eratosthenes.go

يمكن للبرنامج غربلة أول مليون عدد أولي (جميع الأعداد الأولية تصل إلى 15,485,863) في حوالي 10 ثوانٍ.الغربال متزامن، لكن الخوارزمية متزامنة بشكل أساسي:هناك عدد كبير جدًا من نقاط المزامنة المطلوبة بين goroutines ("الممثلين" - إذا أردت) وبالتالي لا يمكنهم التجول بحرية بالتوازي.

Answer 3

البديل الآخر الذي يجب مراعاته هو استخدام الجيل الأولي الاحتمالي.يوجد مثال على ذلك في كتاب جو ("الخادم الرئيسي") الذي يستخدم ميلر رابين على ما أعتقد...

Answer 4

يمكنك العثور على أربعة تطبيقات مختلفة لـ Erlang للعثور على الأعداد الأولية (اثنتان منها تعتمدان على غربال إراتوستينس). هنا.يحتوي هذا الرابط أيضًا على رسوم بيانية تقارن أداء الحلول الأربعة.

Answer 5

إن غربال إراتوستينس سهل التنفيذ إلى حد ما، ولكنه - كما اكتشفت - ليس الأكثر كفاءة.هل قمت بتجربة غربال أتكين؟

غربال أتكين @ ويكيبيديا

Answer 6

خوارزمية الأعداد الأولية المتوازية: http://www.cs.cmu.edu/~scandal/cacm/node8.html

Answer 7

اثنين من مولدات إرلانج الأولية السريعة ذات العملية الواحدة؛يقوم 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.

لا يعد التوليد الأولي بواسطة المناخل مكانًا رائعًا للتزامن (ولكن يمكن استخدام التوازي في التحقق من قابلية القسمة، على الرغم من أن العملية ليست معقدة بما يكفي لتبرير الحمل الإضافي لجميع المرشحات المتوازية التي كتبتها حتى الآن).

`

Answer 8

مشاكل مشروع أويلر (أقول أن معظم المشاكل الخمسين الأولى إن لم يكن أكثر) تتعلق في الغالب بالقوة الغاشمة مع لمسة من البراعة في اختيار حدودك.

تذكر أن تختبر ما إذا كان N أوليًا (بالقوة الغاشمة)، ما عليك سوى معرفة ما إذا كان قابلاً للقسمة على أي عدد أولي حتى الطابق (sqrt(N)) + 1، وليس N/2.

حظ سعيد

Answer 9

أنا أحب مشروع أويلر.

فيما يتعلق بموضوع المولدات الأولية، فأنا من أشد المعجبين بغربال إراتوستينس.

لأغراض الأرقام الأقل من 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، يعمل بسرعة كبيرة.تكمن المشكلة في أنك تبدأ في مواجهة حدود حجم القيمة الخاصة بك بالإضافة إلى طول المصفوفة الخاصة بك.- يساعد التبديل إلى تنفيذ سلسلة أو مصفوفة ثنائية، ولكن لا يزال أمامك التحدي المتمثل في التكرار عبر قائمتك بقيم كبيرة.

Answer 10

هنا نسخة 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