concurrency - Generador principal concurrente

erlang primes

Question

Estoy repasando los problemas en projecteuler.net para aprender a programar en Erlang, y me está costando crear un generador principal que pueda 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 traté de hacer las cosas concurrentes:

-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

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

Answer 2

Amo el Proyecto Euler.

Sobre el tema de los generadores principales, soy un gran admirador de Sieve of Eratosthenes.

A los efectos de los números inferiores a 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 # publicó una lista como esta para 2,000,000 en mucho menos de 1 minuto

Editar: En una nota lateral, el tamiz de Eratóstenes se puede implementar fácilmente y funciona rápidamente, pero se vuelve 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

El tamiz de Eratóstenes es bastante fácil de implementar pero, como habrás descubierto, no es el más eficiente. ¿Has probado el Tamiz de Atkin?

Sieve of Atkin @ Wikipedia

Answer 4

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 al elegir tus límites.

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

Buena suerte

Answer 5

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

Answer 6

El error ''badarity'' significa que estás tratando de llamar a ''diversión'' con una cantidad incorrecta de argumentos. En este caso...

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

La función for / 3 espera una diversión de arity 1, y la función spawn / 1 espera una diversión de arity 0. Pruebe esto en su lugar:

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

La diversión que pasa a engendrar hereda las partes necesarias de su entorno (es decir, I), por lo que no es necesario pasarlo explícitamente.

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, una solución secuencial en, digamos, ML será tan rápida que cualquier número de núcleos no será suficiente para que Erlang lo alcance, y por ejemplo, F # y la Biblioteca de tareas paralelas .NET sería ciertamente un vehículo mucho mejor para este tipo de operaciones.

Answer 7

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

Answer 8

aquí hay 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 generadores primarios erlang rápidos de proceso único; 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).

lazy: lazy / 1 y lazy: next / 1 se refieren a una implementación simple de listas infinitas pseudo-perezosas:

lazy(L) ->
    repeat(L).

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

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

La generación principal por 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

Escribí un tamiz de cebado concurrente de Eratosthenesque usando el Go y los canales.

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

Publiqué sobre esto aquí: http://blog.onideas.ws/eratosthenes.go

El programa puede tamizar el primer millón de primos (todos los primos hasta 15,485,863) en aproximadamente 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.