Generatore principale simultaneo

Question

Sto esaminando i problemi su projecteuler.net per imparare a programmare in Erlang e sto avendo difficoltà a creare un generatore di numeri primi in grado di creare tutti i numeri primi inferiori a 2 milioni, in meno di un minuto.Usando lo stile sequenziale, ho già scritto tre tipi di generatori, incluso il Setaccio di Eratostene, e nessuno di loro funziona abbastanza bene.

Ho pensato che un Sieve simultaneo avrebbe funzionato alla grande, ma ricevo messaggi di bad_arity e non sono sicuro del perché.Qualche suggerimento sul motivo per cui ho il problema o su come codificarlo correttamente?

Ecco il mio codice, le sezioni commentate sono dove ho provato a rendere le cose simultanee:

-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

L'errore 'cattiveria' significa che stai cercando di chiamare un 'divertimento' con il numero sbagliato di argomenti.In questo caso...

%%L = for(1,N, divertimento() -> spawn(divertimento(I) -> aspetta(I,N) fine) fine),

La funzione for/3 si aspetta un fun di arity 1 e la funzione spawn/1 si aspetta un fun di arity 0.Prova questo invece:

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

Il fun passato a spawn eredita le parti necessarie del suo ambiente (vale a dire I), quindi non è necessario passarlo esplicitamente.

Sebbene calcolare i numeri primi sia sempre molto divertente, tieni presente che questo non è il tipo di problema per cui Erlang è stato progettato per risolvere.Erlang è stato progettato per una massiccia concorrenza in stile attore.Molto probabilmente funzionerà piuttosto male su tutti gli esempi di calcolo parallelo dei dati.In molti casi, una soluzione sequenziale, ad esempio, in ML sarà così veloce che un numero qualsiasi di core non sarà sufficiente per consentire a Erlang di recuperare il ritardo, e ad es. F# e la libreria parallela delle attività .NET sarebbe sicuramente un veicolo molto migliore per questo tipo di operazioni.

Answer 2

Ho scritto un crivello primo simultaneo eratostenesco utilizzando i canali Go e.

Ecco il codice: http://github.com/aht/gosieve

Ne ho parlato nel blog qui: http://blog.onideas.ws/eratosthenes.go

Il programma può filtrare il primo milione di numeri primi (tutti i numeri primi fino a 15.485.863) in circa 10 secondi.Il crivello è simultaneo, ma l'algoritmo è principalmente sincrono:ci sono troppi punti di sincronizzazione richiesti tra le goroutine ("attori" -- se preferisci) e quindi non possono vagare liberamente in parallelo.

Answer 3

Un'altra alternativa da considerare è utilizzare la generazione prima probabilistica.C'è un esempio di questo nel libro di Joe (il "server principale") che utilizza Miller-Rabin, credo...

Answer 4

Puoi trovare quattro diverse implementazioni di Erlang per trovare i numeri primi (due delle quali sono basate sul Crivello di Eratostene) Qui.Questo link contiene anche i grafici che mettono a confronto le prestazioni delle 4 soluzioni.

Answer 5

Il Setaccio di Eratostene è abbastanza semplice da implementare ma, come hai scoperto, non è il più efficiente.Hai provato il Setaccio di Atkin?

Setaccio di Atkin @ Wikipedia

Answer 6

Algoritmo parallelo dei numeri primi: http://www.cs.cmu.edu/~scandal/cacm/node8.html

Answer 7

Due generatori erlang prime rapidi a processo singolo;sprimes genera tutti i numeri primi inferiori a 2 m in ~2,7 secondi, fprimes ~3 secondi sul mio computer (Macbook con Core 2 Duo da 2,4 GHz).Entrambi sono basati sul Setaccio di Eratostene, ma poiché Erlang funziona meglio con le liste, piuttosto che con gli array, entrambi mantengono un elenco di numeri primi non eliminati, controllando la divisibilità per il capo corrente e mantenendo un accumulatore di numeri primi verificati.Entrambi implementano anche una ruota primaria per eseguire la riduzione iniziale dell'elenco.

-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 e lazy:next/1 si riferiscono a una semplice implementazione di elenchi infiniti pseudo-pigri:

lazy(L) ->
    repeat(L).

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

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

La generazione primaria tramite setacci non è un ottimo posto per la concorrenza (ma potrebbe usare il parallelismo per verificare la divisibilità, sebbene l'operazione non sia sufficientemente complessa da giustificare il sovraccarico aggiuntivo di tutti i filtri paralleli che ho scritto finora).

`

Answer 8

I problemi del Progetto Eulero (direi che la maggior parte dei primi 50 se non di più) riguardano principalmente la forza bruta con un pizzico di ingegnosità nella scelta dei limiti.

Ricorda di testare qualsiasi se N è primo (con la forza bruta), devi solo vedere se è divisibile per qualsiasi numero primo fino a floor(sqrt(N)) + 1, non N/2.

Buona fortuna

Answer 9

Adoro il Progetto Eulero.

Per quanto riguarda i generatori primi, sono un grande fan del Setaccio di Eratostene.

Per i numeri inferiori a 2.000.000 potresti provare una semplice implementazione del controllo isPrime.Non so come lo faresti in erlang, ma la logica è semplice.

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# ha eseguito un elenco come questo per 2.000.000 ben al di sotto del limite di 1 minuto

Modificare: Nota a margine: il setaccio di Eratostene può essere implementato facilmente e viene eseguito rapidamente, ma diventa ingombrante quando inizi a entrare in elenchi enormi.L'implementazione più semplice, che utilizza un array booleano e valori int, viene eseguita in modo estremamente rapido.Il problema è che inizi a incontrare limiti per la dimensione del tuo valore e per la lunghezza del tuo array.-- Passare a un'implementazione di stringa o bitarray aiuta, ma hai ancora la difficoltà di scorrere l'elenco con valori di grandi dimensioni.

Answer 10

ecco una versione 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