0

コードの実行速度を向上させるために何ができるかについて誰か提案があるかどうか疑問に思っていました. inclusiveSieve of Atkinからすべての素数を含むベクトルを返す関数を作成しました[2, max]。

これが私のコードです。

void atkin_sieve (unsigned int max, std::vector <unsigned int> & primes) {
  // Sieve array up to max defaulted to false
  // Index's [0, max] correspond to numbers
  // Dynamic memory so all values default false
  bool* sieve = new bool [max + 1];
  // Square root of max number
  unsigned int sqrt_max = int (sqrt (max));
  // Unsigned integers declared to save time
  unsigned int n, x, y;

  // TODO - Explain this
  for (x = 1; x < sqrt_max; x++) {
    for (y = 1; y < sqrt_max; y++) {
      n = (4 * x * x) + (y * y);
      if (n <= max && (n % 12 == 1 || n % 12 == 5))
    sieve [n] = !sieve [n];
      n = (3 * x * x) + (y * y);
      if (n <= max && (n % 12 == 7))
    sieve [n] = !sieve [n];
      n = (3 * x * x) - (y * y);
      if (x > y && n <= max && (n % 12 == 11))
    sieve [n] = !sieve [n];
    }
  }

  // TODO - Explain this
  for (x = 5; x < sqrt_max; x++) {
    if (sieve [x]) {
      n = x * x;
      for (y = n; y <= max; y += n)
    sieve [y] = false;
    }
  }

  // Push primes 2, 3, and 5
  primes.push_back(2);
  primes.push_back(3);
  primes.push_back(5);
  // Start from prime 7, skip even numbers
  for (x = 7; x <= max; x += 2) {
    // If the number is prime
    if (sieve [x])
      // Push it into the vector
      primes.push_back(x);
  }

  // Delete the sieve array
  delete [] sieve;
}

この関数を最適化するために何ができるかについて、いくつか質問があります。

sieve 配列をブール値の動的配列として初期化して、デフォルトですべて false になるようにしました。このように sieve を動的にする方が高速ですか、それとも通常の配列のままにしておく必要がありますか?

アルゴリズムが処理された後、for ループを使用してベクトルに素数を格納しています。ふるい内のすべての素数を見つけてベクトルに格納するより高速な方法はありますか?

他のヒント、トリック、ヒント、またはコードは大歓迎です。ありがとうございます。

4

2 に答える 2

0

他の回答が示唆しているように、プロファイリングは時間がどこに行くのかを理解するための最良の方法です.

いくつかの提案とコメント。そのうちのいくつかはおそらく明らかです

  • ふるいの割り当てでゼロの初期化が実際に保証されているとは思いません。そのためには、 を使用する必要がありますbool *sieve = new bool[max+1]();。正常に動作していることがわかった場合は、ここで幸運であるか、デバッグ ビルドをゼロで初期化するコンパイラの下で実行されているかのどちらかです。その場合は、最適化を有効にしてリリース ビルドを試すと、速度が向上することがわかります。

  • 要素ごとに 1 ビットを使用することはほとんどありませbool[]んが、おそらく 1 バイトです。通常、ブール値を密に格納するために特化されているため、より効率的なを使用する場合がありますstd::vector<bool>(ブールごとに 1 ビット)。個々のブール値の読み取り/書き込みの複雑さの増加と、メモリフットプリントの削減とのトレードオフになります。

  • max / log(max)max 未満の素数の数の近似値として、適切な入力検証を使用して、素数配列のサイズを に事前設定してみてください。

  • アプリケーションで関数が繰り返し呼び出されている場合は、以前の sieve 配列を再利用して後続の呼び出しに応答してみてください。

于 2015-04-16T19:03:43.897 に答える
0

返される素数の数によっては、 を使用std::vectorすると問題が発生する可能性があります。その容量を超えるオブジェクトを処理するためにベクターが大きくなるたびに、新しい配列を作成し、古い配列からすべての値を古い配列にコピーする必要があります。新着。この問題を回避std::listするには、またはを使用することを検討してください。std::deque本当に必要な場合はvector、ループして素数の数を数えた方が速い場合があります。その場合reserve、ベクトルが大きくなる必要はありません。

おそらく、コードのプロファイリングを行う必要があります。これを行う方法は、開発環境によって異なります。これにより、コードのほとんどの時間が費やされている場所がわかります。その情報がなければ、結果に大きな影響を与えないコードの一部を最適化するのに何年も費やす可能性があります。

少なくともタイミングコードを追加して、変更が役立つかどうか、およびどの程度役立つかを確認できます。

最良の最適化は、通常、アルゴリズムを変更することです。通常、コードが特にタイム クリティカルでない限り (そうでない場合もあります)、ループのアンローリングなどを実行することは、コンパイラに任せるのが最善です。

また、最適化をオンにしてコンパイルしていることを確認してください。これにより、大きな違いが生じる可能性があります。

于 2015-04-16T06:52:07.317 に答える