Concurrent Prime Generator

Question

Ich werde auf projecteuler.net durch die Probleme zu erfahren, wie in Erlang zu programmieren, und ich bin die härteste Zeit mit einem Prime-Generator zu schaffen, das alle Primzahlen unter 2 Millionen, in weniger als eine Minute zu schaffen. Mit dem sequentiellen Stil habe ich bereits drei Arten von Generatoren geschrieben, darunter das Sieb des Eratosthenes, und keiner von ihnen gut genug durchführen.

dachte ich, eine gleichzeitige Sieve groß funktionieren würde, aber ich bin immer bad_arity Nachrichten, und ich bin nicht sicher, warum. Irgendwelche Vorschläge auf, warum ich habe das Problem, oder wie man es richtig codieren?

Hier ist mein Code, die auf Kommentar Abschnitte sind, wo ich versuchte, die Dinge gleichzeitig zu machen:

-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

Die ‚badarity‘ Fehler bedeuten, dass Sie einen ‚Spaß‘ mit der falschen Anzahl von Argumenten zu nennen versuchen. In diesem Fall ...

%% L = für (1, N, Spaß () -> Laich (fun (I) -> wait (I, N) Ende) Ende)

Die für / 3-Funktion einen Spaß arity erwartet 1 und den Laich / 1 Funktion erwartet ein Spaß arity 0 Try this statt:

L = for(1, N, fun(I) -> spawn(fun() -> wait(I, N) end) end),

Der Spaß zum Laichen vergangen erbt benötigte Teile seiner Umgebung (nämlich I), so gibt es keine Notwendigkeit, es explizit zu übergeben.

Während Primzahlen Berechnung immer viel Spaß gemacht ist, bitte beachten Sie, dass dies nicht die Art von Problem ist Erlang wurde entwickelt, um zu lösen. Erlang wurde für massiven Schauspieler-Stil Parallelität ausgelegt. Es wird höchstwahrscheinlich führen eher schlecht auf alle Beispiele von Daten-parallele Berechnung. In vielen Fällen einer sequentiellen Lösung in, sagen wir, wird ML so schnell sein, dass eine beliebige Anzahl von Kernen wird nicht ausreichen für Erlang bis zu fangen, und zB F # und das .NET-Task-Bibliothek Parallel wäre sicherlich ein viel besseres Fahrzeug für diese Art von Operationen sein.

Answer 2

Ich schrieb einen Eratosthenesque gleichzeitig prime Sieb mit der Go und Kanälen.

Hier ist der Code: http://github.com/aht/gosieve

ich darüber gebloggt hier: http://blog.onideas.ws/eratosthenes.go

Das Programm kann das erste Million Primzahlen (alle Primzahlen bis zu 15.485.863) in etwa 10 Sekunden Sieb heraus. Das Sieb ist gleichzeitig, aber der Algorithmus ist im Wesentlichen synchron. Es viel zu viele Synchronisationspunkte erforderlich zwischen goroutines sind ( „Schauspieler“ - wenn man so will), und somit können sie wandern nicht frei parallel

Answer 3

Eine weitere Alternative zu prüfen, ist probabilistische prime Generation zu verwenden. Es ist ein Beispiel dafür in Joes Buch (der „prime-Server“), die verwendet Miller-Rabin denke ich ...

Answer 4

Sie können vier verschiedene Erlang-Implementierungen für die Suche nach Primzahlen (zwei davon werden auf dem Sieb des Eratosthenes basiert) finden hier . Dieser Link enthält auch Diagramme, die die Leistung der 4 Lösungen verglichen werden.

Answer 5

Das Sieb des Eratosthenes ist ziemlich einfach zu implementieren, aber - wie Sie entdeckt haben - nicht die effizienteste. Haben Sie versucht, das Sieb des Atkin?

Sieve von Atkin @ Wikipedia

Answer 6

Primes parallel Algorithmus: http: //www.cs.cmu. edu / ~ Skandal / CACM / node8.html

Answer 7

Zwei schnelle Single-Prozess erlang prime Generatoren; sprimes erzeugt alle Primzahlen unter 2 m ~ 2,7 Sekunden, fprimes ~ 3 Sekunden auf meinem Computer (Macbook mit einem 2,4 GHz Core 2 Duo). Beide sind auf dem Sieb des Eratosthenes basiert, aber da Erlang am besten mit Listen funktioniert, anstatt Arrays, halten sowohl eine Liste der nicht eliminierten Primzahlen, die Überprüfung für Teilbarkeit durch den aktuellen Kopf und halten einen Akkumulator der verifizierten Primzahlen. Beide auch eine erstklassige Rad implementieren anfängliche Reduktion der Liste zu tun.

-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).

faul: faul / 1 und faul: next / 1 beziehen sich auf eine einfache Implementierung von pseudo-faul unendlichen Listen:

lazy(L) ->
    repeat(L).

repeat(L) -> L++[fun() -> L end].

next([F]) -> F()++[F];
next(L) -> L.

Prime Generation von Sieben ist kein guter Platz für Concurrency (aber es Parallelität bei der Überprüfung auf Teilbarkeit verwenden könnte, obwohl der Betrieb nicht ausreichend komplex ist, den zusätzlichen Aufwand aller parallelen Filter ich bisher geschrieben habe, zu rechtfertigen).

`

Answer 8

Projekt Euler Probleme (ich würde sagen, die meisten der ersten 50, wenn nicht mehr) sind größtenteils über Brute-Force mit einem Schuss Genialität Ihre Grenzen bei der Auswahl.

Denken Sie daran, jeden zu testen, ob N eine Primzahl ist (mit roher Gewalt), können Sie nur dann, wenn seine teilbar durch eine Primzahl bis zu Boden (sqrt (N)) + 1, nicht N / 2.

sehen müssen

Viel Glück

Answer 9

Ich liebe Project Euler.

Zum Thema prime Generatoren, ich bin ein großer Fan des Siebs des Eratosthenes.

Für die Zwecke der Zahlen unter 2000000 Sie können eine einfache isPrime Check Implementierung versuchen. Ich weiß nicht, wie Sie es in erlang tun würden, aber die Logik ist einfach.

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 # eine Liste, wie dies für 2.000.000 in deutlich unter der 1-Minuten-Marke lief

Edit: Auf einer Seite zur Kenntnis, kann das Sieb des Eratosthenes einfach implementiert werden und läuft schnell, aber wird unhandlich, wenn Sie immer in riesige Listen beginnen. Die einfachste Implementierung, einen boolean-Array und int Werten läuft extrem schnell. Das Problem ist, dass Sie für die Größe des Wertes sowie die Länge Ihres Arrays in Grenzen beginnen laufen. - Schalten in einen String oder BitArray Implementierung hilft, aber Sie haben immer noch die Herausforderung der Iterieren durch die Liste bei großen Werten

.

Answer 10

Hier ist eine vb Version

    '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