C＃総理ジェネレータ、ビット配列

Question

（C＃の、プライムジェネレータ） HERESにいくつかのコードの友人をMaxxingと私は上のチャンスをうかがった：のために、私の役立たずのAMDのx64 1800+（デュアルコア）で

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; 
} 

すべての素数は34546.875msで10億以下です。問題は、ビット配列にもっと格納しているようです。 〜20億以上をクランクしようとするのは、そのビットアレイが保存したい以上のものです。それを回避する方法に関するアイデア？

Answer 1

アレイの一部をディスクに「交換」します。つまり、ビットアレイを5億ビットのチャンクに分割してディスクに格納するということです。

メモリは一度に数個しかありません。 C＃（またはその他のOO言語）では、このチャンククラスの中で巨大な配列をカプセル化するのは簡単です。

世代時間は遅いですが、大きなアドレス空間と128ビットのコンパイラが得られるまでは、それほど時間がかかりません。

Answer 2

また、Paxが提案した代替アプローチとして、.NET 4.0の新しいメモリマップファイルクラスを使用して、OSがどの時点でどのチャンクをメモリに入れる必要があるかをOSに決定させます。

しかし、アルゴリズムを最適化して局所性を高めて、ページをメモリの内外にスワップしなくても済むようにしたいと思うことに注意してください（この1文よりも厄介です）。

Answer 3

最大サイズを増やすには、複数の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; 
     } 

Answer 4

ふるいのアルゴリズムは、より良いパフォーマンスだろう。私はそれを使って4分以内にint範囲のすべての32ビット素数（合計約1億500万）を決定することができました。もちろん、素数のリストを返すことは、メモリ要件とは少し違いますが、400 MBを少し超えてしまいます（1 int = 4バイト）。 forループを使用すると、数字がファイルに出力され、さらに楽しくなるようにDBにインポートされました:)しかし、64ビットの素数の場合、プログラムはいくつかの変更を必要とし、おそらく複数のノードにわたって分散実行が必要です。私たちは、今、64ビットのコンパイラを持って、私たちにはない以下のリンク

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

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