Premier générateur simultané

Question

Je vois les problèmes sur projecteuler.net pour apprendre à programmer à Erlang, et j’ai le plus de difficulté à créer un générateur de nombres premiers qui puisse créer tous les nombres premiers inférieurs à 2 millions, en moins d’une minute. En utilisant le style séquentiel, j’ai déjà écrit trois types de générateurs, dont le tamis d’Ératosthène, et aucun d’eux ne fonctionne assez bien.

J'ai pensé qu'un Sieve simultané fonctionnerait très bien, mais je reçois des messages de mauvaise volonté et je ne sais pas pourquoi. Des suggestions sur pourquoi j'ai le problème, ou comment le coder correctement?

Voici mon code, les sections commentées sont celles où j'ai essayé de rendre les choses simultanées:

-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

L'erreur 'badarity' signifie que vous essayez d'appeler un 'amusement' avec un nombre incorrect d'arguments. Dans ce cas ...

%% L = pour (1, N, fun () - > spawn (fun (I) - > attente (I, N) end) end),

La fonction for / 3 attend un amusement d'arity 1 et la fonction spawn / 1 attend un amusement d'arity 0. Essayez plutôt ceci:

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

Le plaisir transmis à spawn hérite des parties nécessaires de son environnement (à savoir I), il n'est donc pas nécessaire de le transmettre explicitement.

Bien que le calcul des nombres premiers soit toujours amusant, gardez à l’esprit que ce n’est pas le genre de problème que Erlang a été conçu pour résoudre. Erlang a été conçu pour une concurrence simultanée massive. Cela fonctionnera probablement plutôt mal sur tous les exemples de calcul parallèle aux données. Dans de nombreux cas, une solution séquentielle dans, disons, ML sera si rapide que un nombre quelconque de noyaux ne suffira pas à Erlang pour le rattraper, et par exemple F # et la bibliothèque parallèle de tâches .NET serait certainement un bien meilleur véhicule pour ce genre d'opérations.

Answer 2

J'ai écrit un tamis principal Eratosthenesque concourant à l'aide des canaux Go et.

Voici le code: http://github.com/aht/gosieve

J'ai blogué à ce sujet ici: http://blog.onideas.ws/eratosthenes.go

Le programme peut filtrer le premier million de nombres premiers (tous les nombres premiers jusqu'à 15 485 863) en 10 secondes environ. Le tamis est simultané, mais l'algorithme est principalement synchrone: il faut beaucoup trop de points de synchronisation entre les goroutines (les "acteurs" - si vous préférez) et ils ne peuvent donc pas se déplacer librement en parallèle.

Answer 3

Une autre alternative à envisager consiste à utiliser la génération principale probabiliste. Il existe un exemple dans le livre de Joe (le "serveur principal") qui utilise Miller-Rabin, je pense ...

Answer 4

Vous pouvez trouver quatre implémentations différentes d'Erlang pour trouver des nombres premiers (deux d'entre elles sont basées sur le tamis d'Eratosthène) ici . Ce lien contient également des graphiques comparant les performances des 4 solutions.

Answer 5

Le tamis d’Ératosthène est assez facile à mettre en œuvre mais, comme vous l’avez découvert, n’est pas le plus efficace. Avez-vous essayé le tamis d’Atkin?

Sieve of Atkin @ Wikipedia

Answer 6

Premier algorithme: http: //www.cs.cmu. edu / ~ scandal / cacm / node8.html

Answer 7

Deux générateurs erlang prime uniques à processus unique; sprimes génère tous les nombres premiers inférieurs à 2 m en ~ 2,7 secondes, puis environ 3 secondes sur mon ordinateur (Macbook avec un processeur à deux gigahertz Core 2 duo). Les deux sont basés sur le tamis d'Eratosthène, mais comme Erlang fonctionne mieux avec des listes plutôt que des tableaux, les deux conservent une liste de nombres premiers non éliminés, vérifiant la divisibilité par la tête actuelle et conservant un accumulateur de nombres premiers vérifiés. Les deux implémentent également une roue principale pour réduire initialement la liste.

-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 et lazy: next / 1 font référence à une implémentation simple de listes infinies pseudo-lazy:

lazy(L) ->
    repeat(L).

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

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

La génération principale par tamis n’est pas un bon endroit pour la concurrence (mais elle pourrait utiliser le parallélisme pour vérifier la divisibilité, bien que l’opération ne soit pas suffisamment complexe pour justifier la surcharge supplémentaire de tous les filtres parallèles que j’ai écrits jusqu’à maintenant).

`

Answer 8

Les problèmes du projet Euler (je dirais que la plupart des 50 premiers sinon plus) sont principalement liés à la force brute, avec une touche d'ingéniosité dans le choix de vos limites.

N'oubliez pas de tester si N est un nombre premier (par la force brute), il vous suffit de voir s'il est divisible par un nombre premier jusqu'au plancher (sqrt (N)) + 1, pas N / 2.

Bonne chance

Answer 9

J'aime le projet Euler.

À propos des générateurs principaux, je suis un grand fan du tamis d’Ératosthène.

Pour les nombres inférieurs à 2 000 000, vous pouvez essayer une simple implémentation de contrôle isPrime. Je ne sais pas comment vous le feriez en erlang, mais la logique est 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 # a lancé une liste comme celle-ci pendant 2 000 000 bien en deçà de la limite d'une minute

Modifier: Notons que le tamis d'Eratosthenes peut être mis en œuvre facilement et fonctionne rapidement, mais devient difficile à manier lorsque vous commencez à vous retrouver avec des listes énormes. La mise en œuvre la plus simple, utilisant un tableau booléen et des valeurs int, est extrêmement rapide. Le problème est que vous commencez à rencontrer des limites pour la taille de votre valeur ainsi que pour la longueur de votre tableau. - Le passage à une implémentation de chaîne ou bitarray peut vous aider, mais vous devez toujours parcourir la liste avec des valeurs élevées.

Answer 10

voici une version 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