1

（C＃、素数ジェネレーター）ここに友人と私が突っついていましたいくつかのコードがあります：

public List<int> GetListToTop(int top)
{            
    top++;
    List<int> result = new List<int>();
    BitArray primes = new BitArray(top / 2);
    int root = (int)Math.Sqrt(top);
    for (int i = 3, count = 3; i <= root; i += 2, count++)
    {
        int n = i - count;
        if (!primes[n])
            for (int j = n + i; j < top / 2; j += i)
            {
                primes[j] = true;
            }
    }
    if (top >= 2)
        result.Add(2);            
    for (int i = 0, count = 3; i < primes.Length; i++, count++)
    {
        if (!primes[i])
        {
            int n = i + count;
            result.Add(n);
        }
    }

    return result;
}

私のドーキーなAMDx641800+（デュアルコア）では、34546.875msで10億未満のすべての素数に対して。問題は、ビット配列により多くを格納しているようです。20億を超えてクランキングしようとすることは、ビット配列が格納したい以上のことです。それを回避する方法について何かアイデアはありますか？

4

4 に答える 4

0

複数のBitArrayを使用して、最大サイズを増やします。数値がビットシフトに優れている場合は、結果をビット配列に格納してビット33〜64を格納します。

BitArray second = new BitArray(int.MaxValue);
long num = 23958923589;
if (num > int.MaxValue)
{
    int shifted = (int)num >> 32;
    second[shifted] = true;
}

long request = 0902305023;
if (request > int.MaxValue)
{
    int shifted = (int)request >> 32;
    return second[shifted];
}
else return first[request];

もちろん、BitArrayがSystem.Numerics.BigIntegerまでのサイズをサポートするのであれば素晴らしいでしょう。
ディスクにスワップすると、コードが非常に遅くなります。
私は64ビットOSを使用しており、BitArrayも32ビットに制限されています。

PS：あなたの素数の計算は奇妙に見えます、私のものは次のように見えます：

for (int i = 2; i <= number; i++)
    if (primes[i])
        for (int scalar = i + i; scalar <= number; scalar += i)
        {
            primes[scalar] = false;
            yield return scalar;
        }
于 2010-05-04T09:13:27.493 に答える
0

アレイの一部をディスクに「スワップ」します。つまり、ビット配列を 5 億ビットのチャンクに分割し、それらをディスクに格納します。

一度にメモリ内に保持できるチャンクはわずかです。C# (またはその他の OO 言語) を使用すると、このチャンキング クラス内に巨大な配列を簡単にカプセル化できます。

代償として生成時間が遅くなりますが、より大きなアドレス空間と 128 ビット コンパイラを入手するまで、それを回避する方法はありません。

于 2009-06-10T06:01:44.193 に答える
0

Sieve アルゴリズムの方がパフォーマンスが優れています。これにより、int 範囲のすべての 32 ビット素数 (合計約 1 億 500 万) を 4 分以内で特定できました。もちろん、メモリ要件が 400 MB (1 int = 4 バイト) を少し超えるため、素数のリストを返すことは別のことです。for ループを使用すると、数値がファイルに出力され、DB にインポートされてさらに楽しくなります :) ただし、64 ビット素数の場合、プログラムにはいくつかの変更が必要であり、複数のノードでの分散実行が必要になる可能性があります。以下のリンクも参考にしてください

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

http://en.wikipedia.org/wiki/Prime-counting_function

于 2010-05-21T05:59:13.153 に答える
0

または、Pax によって提案されたアプローチの代替アプローチとして、.NET 4.0 の新しい Memory-Mapped File クラスを利用し、OS がいつでもどのチャンクをメモリに格納する必要があるかを決定できるようにします。

ただし、メモリ内外でページを不必要にスワップしないように、局所性を高めるためにアルゴリズムを試して最適化する必要があることに注意してください (この 1 つの文が聞こえるよりもトリッキーです)。

于 2009-06-10T06:07:43.823 に答える