Generador principal concurrente

Question

Estoy revisando los problemas en projecteuler.net para aprender a programar en Erlang, y me está costando mucho crear un generador de números primos que pueda crear todos los números primos por debajo de 2 millones, en menos de un minuto.Usando 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 intenté hacer que las cosas sean 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

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

%%L = for(1,N, fun() -> spawn(fun(I) -> esperar(I,N) fin) fin),

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

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

La diversión pasada a spawn hereda partes necesarias de su entorno (es decir, I), por lo que no es necesario pasarla explícitamente.

Si bien calcular números primos siempre es divertido, tenga en cuenta que este no es el tipo de problema para el que Erlang fue diseñado.Erlang fue diseñado para una concurrencia masiva al estilo de los actores.Lo más probable es que funcione bastante mal en todos los ejemplos de cálculo de datos paralelos.En muchos casos, una solución secuencial en, digamos, ML será tan rápido que cualquier número de núcleos no será suficiente para que Erlang se ponga al día y, por ejemplo, F# y la biblioteca paralela de tareas .NET Sin duda sería un vehículo mucho mejor para este tipo de operaciones.

Answer 2

Escribí un tamiz primario concurrente Eratosthenesque usando Go y los canales.

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

Escribí un blog sobre esto aquí: http://blog.onideas.ws/eratosthenes.go

El programa puede filtrar el primer millón de números primos (todos los números primos hasta 15.485.863) en unos 10 segundos.El tamiz es concurrente, pero el algoritmo es principalmente sincrónico:Se requieren demasiados puntos de sincronización entre gorutinas ("actores", si se prefiere) y, por lo tanto, no pueden moverse libremente en paralelo.

Answer 3

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

Answer 4

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

Answer 5

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?

Tamiz de Atkin @ Wikipedia

Answer 6

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

Answer 7

Dos generadores rápidos de erlang prime 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 Core 2 Duo de 2,4 GHz).Ambos se basan en el Tamiz de Eratóstenes, pero dado que Erlang funciona mejor con listas que con matrices, ambos mantienen una lista de números primos no eliminados, verifican la divisibilidad por el jefe actual y mantienen un acumulador de números primos verificados.Ambos también implementan una rueda principal para realizar 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-lazy:

lazy(L) ->
    repeat(L).

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

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

La generación de primos mediante tamices no es un buen 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 8

Los problemas del Proyecto Euler (yo diría que la mayoría de los primeros 50, si no más) tienen que ver principalmente con la fuerza bruta con un toque de ingenio al elegir los límites.

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

Buena suerte

Answer 9

Me encanta el Proyecto Euler.

En cuanto al tema de los generadores primarios, soy un gran admirador del Tamiz de Eratóstenes.

A los efectos de los números inferiores a 2.000.000, puede probar una implementación simple 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# ejecutó una lista como esta para 2.000.000 muy por debajo de la marca de 1 minuto

Editar: Como nota al margen, el tamiz de Eratóstenes se puede implementar fácilmente y se ejecuta rápidamente, pero se vuelve difícil de manejar cuando empiezas a meterte en listas enormes.La implementación más simple, que utiliza una matriz booleana y valores int, se ejecuta extremadamente rápido.El problema es que comienza a encontrarse con límites para el tamaño de su valor así como para la longitud de su matriz.-- Cambiar a una implementación de cadena o matriz de bits ayuda, pero aún tiene el desafío de iterar a través de su lista con valores grandes.

Answer 10

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