Generatore principale simultaneo
-
01-07-2019 - |
Domanda
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.
Soluzione
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.
Altri suggerimenti
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.
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...
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.
Il Setaccio di Eratostene è abbastanza semplice da implementare ma, come hai scoperto, non è il più efficiente.Hai provato il Setaccio di Atkin?
Algoritmo parallelo dei numeri primi: http://www.cs.cmu.edu/~scandal/cacm/node8.html
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).
`
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
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.
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