併發素數生成器

Question

我正在瀏覽projecteuler.net上的問題，以瞭解如何使用Erlang進行編程，而且我最難創建一個能夠創建低於200萬的所有素數的主要生成器，一分鐘。使用順序式，我已經寫了三種類型的生成器，包括Eratosthenes的Sieve，並且它們都不夠好。

我想到一個併發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. 

Answer 1

'badarity'錯誤意味着你試圖用錯誤的方式調用'fun'參數數量。在這種情況下...

%% L =對（1，N，有趣（） - >菌種（FUN（I） - >等待（I，N）端））結束時，

的用於/ 3函數需要arity 1的樂趣，而spawn/1函數需要arity 0的樂趣。試試這個：

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

傳遞到產卵樂趣繼承了其所需環境的部分（即我），所以沒有必要明確地傳遞。

雖然計算素數總是很好玩，但請記住，這不是Erlang設計要解決的問題。 Erlang是爲大規模的演員風格的併發而設計的。在數據並行計算的所有例子中，它很可能表現得相當糟糕。在很多情況下，a sequential solution in, say, ML將會如此之快以至於任何數量的內核都不足以讓Erlang趕上， F# and the .NET Task Parallel Library肯定會成爲這類作業更好的車輛。

Answer 2

我愛項目歐拉。

關於主發電機的問題，我是Eratosthenes的篩子的忠實粉絲。

對於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＃中也跑出這樣的名單2,000,000下1分鐘大關

編輯：在一個側面說明，埃拉托色尼的篩可以輕鬆實現，迅速跑開，但得到當你開始進入巨大的名單時，它是笨拙的。使用布爾數組和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

另一種選擇要考慮的是使用probabalistic黃金一代。在Joe的書（「主服務器」）中有一個例子，它使用Miller-Rabin，我認爲...

Answer 7

您可以找到四種不同的Erlang實現來查找素數（其中兩個基於Eratosthenes的篩選器）here。該鏈接還包含比較4種解決方案性能的圖表。

Answer 8

這裏是一個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 

Answer 9

兩個快速的單工序二郎主要發電機組; sprimes會在〜2.7秒內產生2m以下的所有素數，在我的電腦上使用fprimes〜3秒（帶有2.4 GHz Core 2 Duo的Macbook）。兩者都基於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). 

懶人：懶/ 1和懶惰：下一個/ 1是指一個簡單的實現僞懶惰的無限名單：

lazy(L) -> 
    repeat(L). 

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

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

總理代通過分子篩是不是併發的好地方（但它可以在檢查可分性時使用並行性，儘管該操作不夠複雜，無法證明迄今爲止我寫的所有並行濾波器的額外開銷）。

`

Answer 10

我寫了使用Go和頻道的Eratosthenesque併發素篩。

下面是代碼：http://github.com/aht/gosieve

我的博客上講述在這裏：http://blog.onideas.ws/eratosthenes.go

該程序可以在大約10秒篩出第一百萬素數（所有素數高達15485863）。篩是併發的，但算法主要是同步的：在goroutine（「actors」 - 如果你喜歡）之間需要太多同步點，因此它們不能並行漫遊。