Concurrent Generator Prime

Question

Eu estou passando por problemas no projecteuler.net para aprender a programar em Erlang, e eu estou tendo o momento mais difícil criar um gerador primordial que pode criar todos os números primos abaixo de 2 milhões, em menos de um minuto. Usando o estilo sequencial, já escrevi três tipos de geradores, incluindo o Crivo de Eratóstenes, e nenhum deles executar bem o suficiente.

Eu percebi a Sieve concorrente seria um grande trabalho, mas eu estou recebendo mensagens bad_arity, e eu não sei porquê. Todas as sugestões sobre porque eu tenho o problema, ou como código-lo corretamente?

Aqui está o meu código, as seções comentadas são onde eu tentei fazer as coisas em simultâneo:

-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

significa que o erro 'badarity' que você está tentando chamar uma 'diversão' com o número errado de argumentos. Neste caso ...

%% L = para (1, N, fun () -> desova (diversão (I) -> espera (I, N) end) final),

O para / 3 função espera um divertimento de aridade 1, ea função de desova / 1 espera que um divertimento de arity 0. tentar o seguinte:

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

A diversão passado para herda desova partes necessárias do seu ambiente (ou seja, I), por isso não há necessidade de passá-lo explicitamente.

Ao calcular números primos é sempre uma boa diversão, por favor, mantenha em mente que este não é o tipo de problema Erlang foi projetado para resolver. Erlang foi projetado para enorme concorrência de estilo ator. Ele provavelmente irá executar muito mal em todos os exemplos de computação de dados em paralelo. Em muitos casos, um seqüencial solução em, digamos, ML será tão rápido que qualquer número de núcleos não será suficiente para Erlang de apanhar, por exemplo, e F # E a tarefa .NET Biblioteca paralela de seria certamente um veículo muito melhor para esses tipos de operações.

Answer 2

Eu escrevi uma peneira nobre concorrente Eratosthenesque usando o Go e canais.

Aqui está o código: http://github.com/aht/gosieve

eu escrevi sobre isso aqui: http://blog.onideas.ws/eratosthenes.go

O programa pode peneira o primeiro milhão de números primos (todos os primos upto 15485863) em cerca de 10 segundos. A peneira é concorrente, mas o algoritmo é principalmente síncrona:. Existem demasiados pontos de sincronização necessários entre goroutines ( "atores" - se você quiser) e, portanto, eles não podem andar livremente em paralelo

Answer 3

Outra alternativa a considerar é usar probabalistic geração dos números primos. Há um exemplo disto no livro de Joe (o "servidor prime") que usa Miller-Rabin eu acho ...

Answer 4

Você pode encontrar quatro diferentes implementações Erlang para encontrar números primos (dois dos quais são baseados na Crivo de Eratóstenes) aqui . Este link também contém gráficos que comparam o desempenho das 4 soluções.

Answer 5

O Crivo de Eratóstenes é bastante fácil de implementar, mas - como você descobriu - não o mais eficiente. Você já tentou o Crivo de Atkin?

Crivo de Atkin @ Wikipedia

Answer 6

Primes algoritmo paralelo: http: //www.cs.cmu. edu / ~ escândalo / MCCA / node8.html

Answer 7

Dois rápida single-processo de Erlang geradores principais; sprimes gera todos os números primos menores de 2m em ~ 2,7 segundos, fprimes ~ 3 segundos no meu computador (Macbook com um 2.4 GHz Core 2 Duo). Ambos são baseados no Crivo de Eratóstenes, mas desde Erlang funciona melhor com listas, em vez de matrizes, ambos manter uma lista de números primos não eliminado, a verificação de divisibilidade pelo atual chefe e manter um acumulador de primos verificados. Ambos também implementar uma roda privilegiada para fazer a redução inicial da 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).

preguiçoso: preguiçoso / 1 e preguiçoso: próxima / 1 referem-se a uma implementação simples de pseudo-preguiçoso listas infinitas:

lazy(L) ->
    repeat(L).

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

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

geração Prime por peneiras não é um ótimo lugar para concorrência (mas poderia usar paralelismo na verificação de divisibilidade, embora a operação não é suficientemente complexo para justificar a sobrecarga adicional de todos os filtros paralelos que escrevi até agora).

`

Answer 8

problemas de projeto Euler (eu diria que a maioria da primeira 50 se não mais) são principalmente sobre a força bruta com um toque de criatividade na escolha de seus limites.

Lembre-se de testar qualquer caso N é primo (pela força bruta), você só precisa ver se o seu divisível por qualquer-se privilegiada para andar (sqrt (N)) + 1, não N / 2.

Boa sorte

Answer 9

Eu amo Projeto Euler.

Em matéria de geradores principais, eu sou um grande fã do Crivo de Eratóstenes.

Para efeitos dos números sob 2.000.000 você pode tentar uma implementação verificação isPrime simples. Eu não sei como você faria em Erlang, mas a lógica é simples.

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 # correu uma lista como esta para 2.000.000 em bem abaixo da marca de um minuto

Editar: Em uma nota lateral, a peneira de Eratóstenes pode ser facilmente implementado e executado rapidamente, mas fica complicado quando você começar a entrar em listas enormes. A implementação mais simples, utilizando um booleano valores da matriz e int é executado de forma extremamente rápida. O problema é que você começar a correr em limites para o tamanho de seu valor, bem como a duração da sua matriz. -. A mudança para uma string ou implementação bitarray ajuda, mas você ainda tem o desafio de iteração através de sua lista de grandes valores

Answer 10

aqui é uma versão 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