동시 프라임 생성기
https://stackoverflow.com/questions/89705
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
Erlang에서 프로그래밍하는 방법을 배우기 위해 projecteuler.net에서 문제를 겪고 있는데, 1분 이내에 200만 미만의 소수를 모두 생성할 수 있는 소수 생성기를 만드는 데 가장 어려움을 겪고 있습니다.나는 이미 순차 스타일을 사용하여 에라토스테네스의 체(Sieve of Eratosthenes)를 포함하여 세 가지 유형의 생성기를 작성했지만 그 중 어느 것도 제대로 작동하지 않습니다.
동시 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() -> generate(fun(I) -> wait(I,N) end) end),
for/3 함수는 arity 1의 fun을 기대하고, generate/1 함수는 arity 0의 fun을 기대합니다.대신 이것을 시도해 보세요:
L = for(1, N, fun(I) -> spawn(fun() -> wait(I, N) end) end),
스폰에 전달된 재미는 해당 환경(즉, I)의 필요한 부분을 상속하므로 명시적으로 전달할 필요가 없습니다.
소수를 계산하는 것은 항상 즐거운 일이지만, 이것은 Erlang이 해결하기 위해 고안된 문제가 아니라는 점을 명심하십시오.Erlang은 대규모 액터 스타일 동시성을 위해 설계되었습니다.데이터 병렬 계산의 모든 예에서 성능이 다소 나쁠 가능성이 높습니다.많은 경우에, 예를 들어 ML의 순차 솔루션 너무 빨라서 Erlang이 따라잡기에는 코어 수가 충분하지 않을 것입니다. F# 및 .NET 작업 병렬 라이브러리 확실히 이러한 종류의 작업에 훨씬 더 나은 수단이 될 것입니다.
다른 팁
나는 Go와 채널을 사용하여 Eratosthenesque 동시 프라임 체를 작성했습니다.
코드는 다음과 같습니다. http://github.com/aht/gosieve
나는 여기에 대해 블로그에 글을 올렸습니다: http://blog.onideas.ws/eratosthenes.go
이 프로그램은 약 10초 안에 처음 백만 개의 소수(최대 15,485,863개의 소수)를 걸러낼 수 있습니다.체는 동시적이지만 알고리즘은 주로 동기적입니다.고루틴(원하는 경우 "액터") 간에 필요한 동기화 지점이 너무 많아서 병렬로 자유롭게 로밍할 수 없습니다.
고려해야 할 또 다른 대안은 확률론적 소수 생성을 사용하는 것입니다.Miller-Rabin을 사용하는 Joe의 책("프라임 서버")에 이에 대한 예가 있습니다.
소수를 찾기 위한 네 가지 다른 Erlang 구현을 찾을 수 있습니다(그 중 두 개는 에라토스테네스의 체를 기반으로 함). 여기.이 링크에는 4가지 솔루션의 성능을 비교하는 그래프도 포함되어 있습니다.
에라토스테네스의 체는 구현하기가 매우 쉽지만, 아시다시피 가장 효율적이지는 않습니다.앳킨의 체를 사용해 보셨나요?
소수 병렬 알고리즘: http://www.cs.cmu.edu/~scandal/cacm/node8.html
두 개의 빠른 단일 프로세스 Erlang 소수 생성기;sprimes는 ~2.7초 안에 2m 미만의 모든 소수를 생성하고, 내 컴퓨터(2.4GHz Core 2 Duo가 장착된 Macbook)에서는 fprimes ~3초를 생성합니다.둘 다 에라토스테네스의 체(Sieve of Eratosthenes)를 기반으로 하지만 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이 소수인지(무차별 대입으로) 테스트하는 것을 기억하세요. N/2가 아닌 Floor(sqrt(N)) + 1까지 소수로 나눌 수 있는지 확인하면 됩니다.
행운을 빌어요
저는 프로젝트 오일러를 좋아합니다.
프라임 제너레이터에 관해 저는 에라토스테네스의 체(Sieve of Eratosthenes)의 열렬한 팬입니다.
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#은 1분이 채 안 되는 시간에 2,000,000에 대해 이와 같은 목록을 실행했습니다.
편집하다: 참고로 에라토스테네스의 체는 쉽게 구현되고 빠르게 실행될 수 있지만 거대한 목록에 들어가기 시작하면 다루기가 어려워집니다.부울 배열과 int 값을 사용하는 가장 간단한 구현은 매우 빠르게 실행됩니다.문제는 값의 크기와 배열의 길이에 대한 제한이 시작된다는 것입니다.-- 문자열 또는 비트 배열 구현으로 전환하면 도움이 되지만 여전히 큰 값에서 목록을 반복해야 하는 문제가 있습니다.
여기 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
