concurrency - コンカレント プライム ジェネレーター

Question

私は projecteuler.net の問題を解いて Erlang でのプログラミング方法を学んでいますが、200 万未満の素数をすべて 1 分以内に作成できる素数ジェネレータを作成するのに最も苦労しています。シーケンシャル スタイルを使用して、エラトステネスのふるいを含む 3 種類のジェネレーターを既に作成しましたが、どれも十分に機能しません。

並行 Sieve がうまく機能すると考えましたが、bad_arity メッセージが表示され、その理由がわかりません。なぜ私が問題を抱えているのか、または適切にコーディングする方法について何か提案はありますか?

これが私のコードです。コメントアウトされたセクションは、私が物事を並行させようとした場所です:

-モジュール (プライムサーバー)。
-compile(export_all)。

開始() ->
    register(primes, spawn(fun() -> loop() end)))。

is_prime(N) -> rpc({is_prime,N})。

rpc(リクエスト) ->
    素数！{self(), リクエスト},
    受け取る
        {素数、応答} ->
            応答
    終わり。

ループ() ->
    受け取る
        {From, {is_prime, N}} ->
            もしも
                Nから！{素数、偽};
                N =:= 2 -> から ! {素数、真};
                N レム 2 =:= 0 -> から ! {素数、偽};
                真 ->
                    値 = is_not_prime(N),
                    Val = not(lists:member(true, Values)),
                    から ！{プライム、ヴァル}
            終わり、
            ループ（）
    終わり。

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) I + S > N -> [F(I)] の場合。

get_list(I, リミット) ->
    もしも
        私
            [私*A || あ
            []
    終わり。

is_not_prime(N) ->
    for(3, N, 2,
        楽しい(私) ->
            List = get_list(I,trunc(N/I)),
            リスト:メンバー(N,リスト:フラット化(リスト))
        終わり
        ）。

    %%L = for(1,N, fun() -> spawn(fun(I) -> wait(I,N) end) end),
    %%SeedList = [A || あ  
    %% リスト:foreach(fun(X) ->
    %%ピッド! {リスト内、X}
    %% 終了, SeedList)
    %% エンド、L)。

%%wait(I,N) ->
%% リスト = [I*A || リスト:メンバー(X,リスト)
％％ 終わり。

Answer 1

Go とチャネルを使用して、Eratosthenesque 並列素数ふるいを作成しました。

コードは次のとおりです。http://github.com/aht/gosieve

ここでブログを書きました：http://blog.onideas.ws/eratosthenes.go

このプログラムは、約 10 秒で最初の 100 万個の素数 (15,485,863 までのすべての素数) をふるいにかけることができます。ふるいは並行していますが、アルゴリズムは主に同期的です。ゴルーチン (「アクター」- 必要に応じて) 間で必要な同期ポイントが多すぎるため、並行して自由に移動できません。

Answer 2

「badarity」エラーは、間違った数の引数で「fun」を呼び出そうとしていることを意味します。この場合...

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

for/3 関数はアリティ 1 の fun を期待し、spawn/1 関数はアリティ 0 の fun を期待します。代わりにこれを試してください:

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

spawn に渡される fun は、その環境 (つまり I) の必要な部分を継承するため、明示的に渡す必要はありません。

素数の計算は常に楽しいものですが、これは Erlang が解決するように設計された種類の問題ではないことを覚えておいてください。Erlang は、大規模なアクター スタイルの並行性のために設計されました。ほとんどの場合、データ並列計算のすべての例でパフォーマンスがかなり悪くなります。多くの場合、たとえば ML でのシーケンシャル ソリューションは非常に高速であるため、Erlang が追いつくにはいくつのコアでも十分ではありません。たとえば、F# と .NET Task Parallel Libraryは、これらの種類のソリューションには確実に優れた手段となるでしょう。操作の。

Answer 3

考慮すべきもう 1 つの方法は、確率的素数生成を使用することです。Miller-Rabinを使用するJoeの本（「プライムサーバー」）にこれの例があります...

Answer 4

素数を見つけるための 4 つの異なる Erlang 実装 (そのうちの 2 つはエラトステネスのふるいに基づいています) をここで見つけることができます。このリンクには、4 つのソリューションのパフォーマンスを比較するグラフも含まれています。

Answer 5

エラトステネスのふるいはかなり簡単に実装できますが、お気づきのとおり、最も効率的ではありません。アトキンのふるいを試しましたか？

アトキンのふるい @ ウィキペディア

Answer 6

素数並列アルゴリズム: http://www.cs.cmu.edu/~scandal/cacm/node8.html

Answer 7

2 つの高速な単一プロセス erlang プライム ジェネレーター。sprimes は、私のコンピューター (2.4 GHz Core 2 Duo を搭載した Macbook) で ~2.7 秒、fprimes ~3 秒で 2m 未満のすべての素数を生成します。どちらもエラトステネスのふるいに基づいていますが、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.

Sieves による素数生成は、同時実行には最適な場所ではありません (ただし、これまでに記述したすべての並列フィルターの追加オーバーヘッドを正当化するほど操作は複雑ではありませんが、可分性のチェックに並列処理を使用できます)。

`

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

私はプロジェクト・オイラーが大好きです。

素数発生器に関して言えば、私はエラトステネスのふるいの大ファンです。

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# は、1 分をはるかに下回る 2,000,000 に対して、このようなリストを実行しました

編集: 余談ですが、エラトステネスのふるいは簡単に実装でき、すばやく実行できますが、巨大なリストに入ると扱いにくくなります。ブール配列と int 値を使用する最も単純な実装は、非常に高速に実行されます。問題は、値のサイズと配列の長さの制限に達し始めることです。-- 文字列またはビット配列の実装への切り替えは役に立ちますが、大きな値でリストを反復処理するという課題がまだ残っています。

Answer 10

Project Euler の問題 (最初の 50 のほとんどは、それ以上ではないにしても) は、ほとんどの場合、境界を選択する際の創意工夫を伴う総当りに関するものです。

N が素数であるかどうかを (力ずくで) テストすることを忘れないでください。N/2 ではなく、floor(sqrt(N)) + 1 までの任意の素数で割り切れるかどうかだけを確認する必要があります。

幸運を