13

私は実際に私の質問に対する答えを持っていますが、それは並列化されていないので、アルゴリズムを改善する方法に興味があります. とにかく、一部の人にとってはそのままで役立つかもしれません。

int Until = 20000000;
BitArray PrimeBits = new BitArray(Until, true);

/*
 * Sieve of Eratosthenes
 * PrimeBits is a simple BitArray where all bit is an integer
 * and we mark composite numbers as false
 */

PrimeBits.Set(0, false); // You don't actually need this, just
PrimeBits.Set(1, false); // remindig you that 2 is the smallest prime

for (int P = 2; P < (int)Math.Sqrt(Until) + 1; P++)
    if (PrimeBits.Get(P))
        // These are going to be the multiples of P if it is a prime
        for (int PMultiply = P * 2; PMultiply < Until; PMultiply += P)
            PrimeBits.Set(PMultiply, false);

// We use this to store the actual prime numbers
List<int> Primes = new List<int>();

for (int i = 2; i < Until; i++)
    if (PrimeBits.Get(i))
        Primes.Add(i);

複数BitArrayの s とBitArray.And()を一緒に使用できますか?

4

8 に答える 8

7

ビット配列を双方向リンク リストと相互参照することで時間を節約できるため、次の素数にすばやく進むことができます。

また、新しい素数 p を初めてヒットすると、後の合成を削除すると、残りの p の最初の合成倍数は p*p になります。これは、それ以前のすべてが既に削除されているためです。実際には、p にリスト内のその後に残っているすべての潜在的な素数を掛けるだけでよく、積が範囲外 (Until より大きい) になるとすぐに停止します。

Miller-Rabin 検定など、優れた確率的アルゴリズムもいくつかあります。 ウィキペディアのページは良い紹介です。

于 2008-08-29T09:08:27.030 に答える
4

並列化はさておき、すべての反復でsqrt（Until）を計算する必要はありません。また、2、3、および5の倍数を想定し、{1,5}のN％6または{1,7,11,13,17,19,23,29}のN％30のみを計算することもできます。

N番目のステージはsqrt（n）番目の結果にのみ依存するため、因数分解アルゴリズムを非常に簡単に並列化できるはずです。しばらくすると、競合は発生しなくなります。しかし、それは多くの除算を必要とするため、良いアルゴリズムではありません。

読み取り前に完了することが保証されているライター作業パケットがある場合は、ふるいアルゴリズムを並列化できる必要もあります。ほとんどの場合、ライターはリーダーと競合しないはずです。少なくともいくつかのエントリを実行すると、リーダーより少なくともN上で動作するはずなので、同期読み取りが必要になるのはごくまれです（Nが最後の同期読み取りを超える場合）。価値）。書き込みの競合は発生しないため、bool配列を任意の数のライタースレッド間で同期する必要はありません（最悪の場合、複数のスレッドが同じ場所にtrueを書き込みます）。

主な問題は、書き込みを待機しているすべてのワーカーが完了していることを確認することです。C ++では、比較と設定を使用して、任意の時点で待機しているワーカーに切り替えます。私はC＃の専門家ではないので、その言語でそれを行う方法はわかりませんが、Win32InterlockedCompareExchange関数が使用可能である必要があります。

また、アクターベースのアプローチを試すこともできます。これにより、アクターが最小値で動作するようにスケジュールできるため、 N。

いずれにせよ、読む前にすべてのワーカーがエントリNを超えていることを確認する必要があります。そのためのコストは、パラレルとシリアルの間のトレードオフが行われる場所です。

于 2008-08-27T20:52:54.093 に答える
1

プロファイリングを行わないと、プログラムのどの部分を最適化する必要があるかわかりません。

大規模なシステムを使用している場合は、プロファイラーを使用して、素数ジェネレーターが最適化が必要な部分であることを確認します。

十数個の命令を含むループをプロファイリングすることは、通常、あまり価値がありません。プロファイラーのオーバーヘッドは、ループ本体と比較して重要です。ループを改善する唯一の方法は、アルゴリズムを変更して反復回数を減らすことです。 . したがって、IME では、コストのかかる関数をすべて削除し、数行の単純なコードの既知のターゲットを取得したら、命令レベルでコードを改善しようとするよりも、アルゴリズムを変更してエンド ツー エンドの実行のタイミングを計った方がよいでしょう。プロファイリング。

于 2008-09-04T20:38:54.093 に答える
0

@DrPizzaプロファイリングは、実装の改善に役立つだけであり、並列実行の機会を明らかにしたり、より良いアルゴリズムを提案したりすることはありません（他の経験がない限り、プロファイラーを実際に見たいと思います）。

私は自宅にシングルコアマシンしかありませんが、BitArrayふるいに相当するJavaと、ふるいの反転のシングルスレッドバージョンを実行しました-配列内のマーキング素数を保持し、ホイールを使用して検索スペースを削減します5の因数で、各マーキング素数を使用してホイールの増分でビット配列をマーキングします。また、ストレージをO（N）ではなくO（sqrt（N））に削減します。これは、最大のN、ページング、および帯域幅の両方の点で役立ちます。

Nの中間値（1e8から1e12）の場合、sqrt（N）までの素数を非常にすばやく見つけることができ、その後、CPUでの後続の検索を非常に簡単に並列化できるはずです。私のシングルコアマシンでは、ホイールアプローチは28秒で1e9までの素数を検出しますが、ふるい（sqrtをループから外した後）は86秒かかります-改善はホイールによるものです。反転とは、2 ^ 32より大きいNを処理できることを意味しますが、処理が遅くなります。コードはここにあります。sqrt（N）を通過した後も、ナイーブシーブからの結果の出力を並列化できます。これは、その時点以降、ビット配列が変更されないためです。しかし、Nを処理するのに十分な大きさであると、配列サイズがintに対して大きすぎます。

于 2008-09-01T00:06:01.740 に答える
0

また、アルゴリズムの変更の可能性も考慮する必要があります。

要素を見つけ次第、単にリストに追加する方がコストがかからない可能性があることを考慮してください。

おそらく、リストにスペースを事前に割り当てると、作成/入力が安くなります。

于 2008-09-17T01:43:13.213 に答える
0

エラトステネスのふるいに関する非常に優れた記事があります: The Genuine Sieve of Eratosthenes

これは機能的な設定ですが、ほとんどの最適化は C# での手続き型の実装にも適用されます。

最も重要な 2 つの最適化は、2*P ではなく P^2 でクロスアウトを開始することと、次の素数にホイールを使用することです。

並行性については、不要な作業を行わずに P^2 までのすべての数値を P と並行して処理できます。

于 2008-09-17T07:15:11.747 に答える
0

新しい素数を見つけようとしていますか? これはばかげているように聞こえるかもしれませんが、既知の素数を使用してある種のデータ構造をロードできる可能性があります。誰かがリストを持っていると確信しています。新しい数値を計算する既存の数値を見つける方がはるかに簡単な問題かもしれません。

また、マルチコア システムを利用するために既存のコードをマルチスレッド化するために、MicrosoftのParallel FX Libraryを参照することもできます。最小限のコード変更で、for ループをマルチスレッド化できます。

于 2008-09-17T01:57:54.473 に答える