Параллельный первичный генератор

Question

Я сталкиваюсь с проблемами на projecteuler.net, чтобы узнать, как программировать в Erlang, и у меня сложнее всего создать генератор простых чисел, который может создавать все простые числа ниже 2 миллионов, меньше минута. Используя последовательный стиль, я уже написал три типа генераторов, в том числе сито Эратосфена, и никто из них не работает достаточно хорошо.

Я решил, что параллельное сито будет работать отлично, но я получаю сообщения о плохом образе, и я не уверен, почему. Любые предложения о том, почему у меня есть проблема, или как правильно ее закодировать?

Вот мой код, Закомментированный из секции, где я пытался сделать вещи одновременно:

 
-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

Ошибка «badarity» означает, что вы пытаетесь назвать «забавой» с неправильным количество аргументов. В этом случае ...

%% L = для (1, N, весело() -> икру (забава (I) -> ждать (I, N) конец) конец),

для/3 ожидает веселья arity 1, а функция spawn/1 ожидает удовольствия от arity 0.Попробуйте вместо этого:

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

Весело прошел нерест наследует нужны части своей среды (а именно я), так что нет необходимости передавать его в явном виде.

При расчете простых чисел всегда весело, пожалуйста, имейте в виду, что это не та проблема, с которой Эрланг был разработан. Эрланг был разработан для массового актуарного параллелизма. Скорее всего, он будет работать довольно плохо на всех примерах параллельных вычислений данных. Во многих случаях a sequential solution in, say, ML будет настолько быстрым, что любое количество ядер не будет достаточным для того, чтобы Erlang мог догнать, и, например, F# and the .NET Task Parallel Library, безусловно, будет гораздо лучшим средством для таких операций.

Answer 2

Я люблю Проект Эйлера.

Что касается главных генераторов, я большой поклонник сита Эратосфена.

Для целей, превышающих 2 000 000, вы можете попробовать простую реализацию проверки isPrime. Я не знаю, как вы это сделаете в erlang, но логика проста.

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# побежал список как это для 2000000 в хорошо под 1-й минуте

Edit:На стороне записки, решето Эратосфена может быть легко реализована и работает быстро, но получает громоздкий, когда вы начинаете попадать в огромные списки. Простейшая реализация, использующая логический массив и значения int, выполняется очень быстро. Беда в том, что вы начинаете работать с ограничениями на размер вашего значения, а также на длину вашего массива. - Переключение на реализацию строки или bitarray помогает, но у вас все еще есть проблема с повторением через ваш список при больших значениях.

Answer 3

Проблемы с проектом Эйлера (я бы сказал, что большинство из первых 50, если не больше) в основном касаются грубой силы с всплеском изобретательности в выборе границ.

Не забудьте проверить, если N является простым (по грубой силе), вам нужно только увидеть, может ли он делиться на любой простой до пола (sqrt (N)) + 1, а не N/2.

Успехов

Answer 4

решета Эратосфена довольно легко осуществить, но - как вы обнаружили, - не самый эффективный. Вы пробовали сито Аткина?

Sieve of Atkin @ Wikipedia

Answer 5

Штрихов параллельный алгоритм: http://www.cs.cmu.edu/~scandal/cacm/node8.html

Answer 6

Другой альтернатива для рассмотрения является использование вероятностного простого поколения. Вот пример этого в книге Джо («главный сервер»), который использует Миллер-Рабин, я думаю ...

Answer 7

Вы можете найти четыре различных варианта Erlang для нахождения простых чисел (два из которых основаны на сите эратосфенов) here. Эта ссылка также содержит графики, сравнивающие производительность четырех решений.

Answer 8

здесь является В.Б версией

'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

Два быстрых Erlang однопроцессных простых генераторов; sprimes генерирует все простые числа менее 2 м в ~ 2,7 секунды, fprimes ~ 3 секунды на моем компьютере (Macbook с 2,4 ГГц Core 2 Duo). Оба они основаны на Сите Эратосфена, но поскольку Эрланг лучше всего работает со списками, а не с массивами, они сохраняют список не исключенных простых чисел, проверяя делимость на текущую голову и сохраняя аккумулятор проверенных простых чисел. Оба также реализуют основное колесо для первоначального сокращения списка.

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

ленивый: ленивый/1 и ленивый: следующий/1 относятся к простой реализации псевдо-ленивой бесконечных списков:

lazy(L) -> 
    repeat(L). 

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

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

премьера поколение на ситах не является отличным место для параллельности (но он может использовать параллелизм при проверке на делимость, хотя операция недостаточно сложна, чтобы оправдать дополнительные накладные расходы всех параллельных фильтров, которые я написал до сих пор).

`

Answer 10

я написал Eratosthenesque параллельное простое сито, используя Go и каналы.

Вот код: http://github.com/aht/gosieve

Я писал о нем здесь: http://blog.onideas.ws/eratosthenes.go

Программа может отсеивать первый миллион простых чисел (все простые числа Шифрование до 15,485,863) в течение примерно 10 секунд. Сито является параллельным, но алгоритм в основном синхронный: слишком много точек синхронизации, требуемых между горутами («актеры» - если хотите), и поэтому они не могут свободно перемещаться параллельно.