Concurrent Prime Generator

Question

Estoy pasando por los problemas en projecteuler.net para aprender a programar en Erlang, y estoy teniendo el momento más difícil de crear un generador principal que puede crear todos los números primos por debajo de 2 millones, en menos de un minuto. Utilizando el estilo secuencial, ya he escrito tres tipos de generadores, incluido el tamiz de Eratóstenes, y ninguno de ellos funciona lo suficientemente bien.

Pensé que un Sieve simultáneo funcionaría muy bien, pero recibo mensajes de bad_arity, y no estoy seguro de por qué. ¿Alguna sugerencia sobre por qué tengo el problema o cómo codificarlo correctamente?

Aquí está mi código, las secciones comentadas son donde he intentado hacer las cosas concurrente:

 
-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

El error 'badarity' significa que estás tratando de llamar 'diversión' con el error numero de argumentos En este caso ...

%% L = a (1, N, diversión() -> desove (divertido (I) -> espera (I, N) final) final),

La de/3 función espera una diversión de arity 1, y la función spawn/1 espera una diversión de arity 0.Prueba este lugar:

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

La diversión pasó a desovar hereda partes de su entorno sea necesario (es decir, I), así que no hay necesidad de pasar de forma explícita.

Si bien el cálculo de números primos siempre es divertido, tenga en cuenta que este no es el tipo de problema que Erlang fue diseñado para resolver. Erlang fue diseñado para una concurrencia masiva de estilo actor. Lo más probable es que funcione bastante mal en todos los ejemplos de computación paralela a los datos. En muchos casos, a sequential solution in, say, ML será tan rápido que cualquier cantidad de núcleos no será suficiente para que Erlang se ponga al día, y p. F# and the .NET Task Parallel Library sin duda sería un vehículo mucho mejor para este tipo de operaciones.

Answer 2

Me encanta Proyecto Euler.

En cuanto a los generadores principales, soy un gran admirador de Sieve of Eratosthenes.

Para propósitos de los números por debajo de 2,000,000, puede intentar con una simple implementación de verificación isPrime. No sé cómo lo harías en Erlang, pero la lógica es simple.

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# corrió una lista como esta para 2.000.000 en muy por debajo del minuto 1

Editar:En una nota, la criba de Eratóstenes se puede implementar fácilmente y se extiende rápidamente, pero se difícil de manejar cuando empiezas a entrar en listas enormes. La implementación más simple, utilizando una matriz booleana y valores int, se ejecuta extremadamente rápido. El problema es que comienzas a encontrar límites para el tamaño de tu valor y la longitud de tu matriz. - Cambiar a una implementación de cadena o bitarray ayuda, pero todavía tiene el desafío de iterar a través de su lista en valores grandes.

Answer 3

Los problemas del proyecto Euler (diría que la mayoría de los primeros 50, si no más) se refieren principalmente a la fuerza bruta con un toque de ingenio en la elección de sus límites.

Recuerde probar cualquier si N es primo (por fuerza bruta), solo necesita ver si es divisible por cualquier prima hasta el piso (sqrt (N)) + 1, no N/2.

Buena suerte

Answer 4

La criba de Eratóstenes es bastante fácil de aplicar, pero - como has descubierto - no es el más eficiente. ¿Has probado el Tamiz de Atkin?

Sieve of Atkin @ Wikipedia

Answer 5

Primes algoritmo paralelo: http://www.cs.cmu.edu/~scandal/cacm/node8.html

Answer 6

Otra alternativa a considerar es el uso de la generación de primer probabilística. Hay un ejemplo de esto en el libro de Joe (el "servidor principal") que usa Miller-Rabin, creo ...

Answer 7

Puede encontrar cuatro implementaciones diferentes de Erlang para encontrar números primos (dos de los cuales se basan en el Tamiz de Eratóstenes) here. Este enlace también contiene gráficos que comparan el rendimiento de las 4 soluciones.

Answer 8

aquí es una versión 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 

Answer 9

Dos rápida de Erlang solo proceso principales generadores; sprimes genera todos los números primos por debajo de 2 m en ~ 2.7 segundos, fprimes ~ 3 segundos en mi computadora (Macbook con un Core 2 Duo de 2.4 GHz). Ambos están basados ​​en el Tamiz de Eratóstenes, pero como Erlang funciona mejor con listas, en lugar de matrices, ambos mantienen una lista de primos no eliminados, verificando la divisibilidad por el jefe actual y manteniendo un acumulador de primos verificados. Ambos también implementan una rueda principal para hacer la reducción inicial de la lista.

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

perezoso: perezoso/1 y perezoso: siguiente/1 se refieren a una simple aplicación de listas infinitas seudo-perezoso:

lazy(L) -> 
    repeat(L). 

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

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

primer generación de tamices no es un gran lugar para la concurrencia (pero podría usar el paralelismo para verificar la divisibilidad, aunque la operación no es lo suficientemente compleja como para justificar la sobrecarga adicional de todos los filtros paralelos que he escrito hasta ahora).

`

Answer 10

I escribió un tamiz primer concurrente Eratosthenesque usando el Go y canales.

Aquí está el código: http://github.com/aht/gosieve

blogged sobre él aquí: http://blog.onideas.ws/eratosthenes.go

El programa puede tamizar a cabo el primer millón de números primos (todos los números primos upto 15485863) en unos 10 segundos. El tamiz es concurrente, pero el algoritmo es principalmente sincrónico: se requieren demasiados puntos de sincronización entre goroutines ("actores", si se quiere) y por lo tanto no pueden moverse libremente en paralelo.