Параллельный простой генератор
https://stackoverflow.com/questions/89705
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я решаю задачи на projecteuler.net, чтобы научиться программировать на Erlang, и мне сложнее всего создать генератор простых чисел, который сможет создать все простые числа ниже 2 миллионов менее чем за минуту.Используя последовательный стиль, я уже написал три типа генераторов, включая «Решето Эратосфена», и ни один из них не работает достаточно хорошо.
Я подумал, что параллельное Sieve будет отлично работать, но я получаю сообщения bad_arity и не знаю почему.Есть какие-нибудь предложения о том, почему у меня возникла проблема или как правильно ее закодировать?
Вот мой код, в закомментированных разделах я пытался сделать все одновременно:
-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.
Решение
Ошибка «badarity» означает, что вы пытаетесь вызвать «fun» с неверным количеством аргументов.В этом случае...
%%L = for(1,N, fun() -> spawn(fun(I) -> wait(I,N) end) end),
Функция for/3 ожидает удовольствие с арностью 1, а функция spawn/1 ожидает удовольствие с арностью 0.Вместо этого попробуйте это:
L = for(1, N, fun(I) -> spawn(fun() -> wait(I, N) end) end),
Fun, передаваемый в spawn, наследует необходимые части своего окружения (а именно меня), поэтому нет необходимости передавать его явно.
Хотя вычисление простых чисел всегда доставляет массу удовольствия, имейте в виду, что Erlang не предназначен для решения этой проблемы.Erlang был разработан для массового параллелизма в стиле актеров.Скорее всего, он будет работать довольно плохо на всех примерах параллельных вычислений.Во многих случаях, последовательное решение, скажем, в ML будет настолько быстрым, что Erlang не сможет догнать любое количество ядер, и, например, F# и библиотека параллельных задач .NET безусловно, будет гораздо лучшим средством для такого рода операций.
Другие советы
Я написал параллельное простое решето в стиле Эратосфена, используя Go и каналы.
Вот код: http://github.com/aht/gosieve
Я писал об этом здесь: http://blog.onideas.ws/eratosthenes.go
Программа может отсеять первый миллион простых чисел (все простые числа до 15 485 863) примерно за 10 секунд.Решето является параллельным, но алгоритм в основном синхронный:между горутинами («актёрами» — если хотите) требуется слишком много точек синхронизации, и поэтому они не могут свободно перемещаться параллельно.
Другая альтернатива, которую следует рассмотреть, — это использование вероятностной генерации простых чисел.В книге Джо есть пример («главный сервер»), в котором, я думаю, используется Миллер-Рабин...
Вы можете найти четыре различные реализации Erlang для поиска простых чисел (две из которых основаны на решете Эратосфена). здесь.Эта ссылка также содержит графики, сравнивающие производительность четырех решений.
Решето Эратосфена довольно легко реализовать, но, как вы обнаружили, оно не самое эффективное.Пробовали ли вы «Сито Аткина»?
Параллельный алгоритм простых чисел: http://www.cs.cmu.edu/~scandal/cacm/node8.html
Два быстрых однопроцессных генератора простых чисел Эрланга;sprimes генерирует все простые числа длиной менее 2 м примерно за 2,7 секунды, fprimes — за 3 секунды на моем компьютере (Macbook с процессором Core 2 Duo 2,4 ГГц).Оба основаны на Решете Эратосфена, но поскольку Erlang лучше всего работает со списками, а не с массивами, оба хранят список неисключенных простых чисел, проверяя делимость на текущую головку и сохраняя аккумулятор проверенных простых чисел.Оба также реализуют простое колесо для первоначального сокращения списка.
-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 и lazy:next/1 относятся к простой реализации псевдоленивых бесконечных списков:
lazy(L) ->
repeat(L).
repeat(L) -> L++[fun() -> L end].
next([F]) -> F()++[F];
next(L) -> L.
Генерация простых чисел с помощью сит не является лучшим местом для параллелизма (но при проверке на делимость можно использовать параллелизм, хотя операция недостаточно сложна, чтобы оправдать дополнительные накладные расходы всех параллельных фильтров, которые я написал до сих пор).
`
Задачи проекта Эйлера (я бы сказал, что большая часть первых 50, если не больше) в основном связаны с грубой силой и некоторой изобретательностью в выборе границ.
Не забудьте проверить любое простое число N (грубым перебором), вам нужно только проверить, делится ли оно на любое простое число до Floor(sqrt(N)) + 1, а не на N/2.
Удачи
Я люблю проект Эйлера.
Что касается генераторов простых чисел, я большой поклонник «Решета Эратосфена».
Для чисел меньше 2 000 000 вы можете попробовать простую реализацию проверки isPrime.Я не знаю, как бы вы это сделали на Эрланге, но логика проста.
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# выполнил такой список для 2 000 000 менее чем за 1 минуту
Редактировать: Кстати, решето Эратосфена можно легко реализовать и работать быстро, но оно становится громоздким, когда вы начинаете работать с огромными списками.Простейшая реализация с использованием логического массива и целочисленных значений выполняется очень быстро.Проблема в том, что вы начинаете сталкиваться с ограничениями на размер вашего значения, а также на длину вашего массива.-- Переключение на реализацию строки или битового массива помогает, но у вас все равно остается проблема с перебором списка с большими значениями.
вот версия 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
