エラトステネスのC++ふるい

Question

私は400万人以下の素数を見つけようとしていますが、私のコードは8秒で実行されています。私は間違って何をしていますか？

私はそれをより速くするために何ができますか？

#include<iostream> 
#include<math.h> 
#include<vector> 
using namespace std; 
int main() 
{ 
    vector<bool> k;       
    vector<long long int> c;     
    for (int i=2;i<40000000;i++) 
    { 
     k.push_back(true);     
     c.push_back(i); 
    } 

    for (int i=0;i<sqrt(40000000)+1;i++)        
    {                
     if (k[i]==true)            
     {                
      for (int j=i+c[i];j<40000000;j=j+c[i])     
      {              
       k[j]=false; 
      } 
     } 
    } 
    vector <long long int> arr; 
    for (int i=0;i<40000000-2;i++) 
    { 
     if (k[i]==true) 
     { 
      arr.push_back(c[i]); 
     } 
    } 
    cout << arr.size() << endl ; 
    return 0; 
} 

Answer 1

私はあなたのコードだけでなく、以下の簡単な調整も行いました。微調整は、二倍の速さ以上のものです：ここでは

auto start = std::chrono::high_resolution_clock::now(); 

    //original version 
    vector<bool> k;       
    vector<long long int> c;     
    for (int i=2;i<40000000;i++) 
     { 
     k.push_back(true);     
     c.push_back(i); 
     } 

    for (int i=0;i<sqrt(40000000)+1;i++)        
     {                
     if (k[i]==true)            
      {                
      for (int j=i+c[i];j<40000000;j=j+c[i])     
       {              
       k[j]=false; 
       } 
      } 
     } 
    vector <long long int> arr; 
    for (int i=0;i<40000000-2;i++) 
     { 
     if (k[i]==true) 
      { 
      arr.push_back(c[i]); 
      } 
     } 
    cout << arr.size() << endl ; 


    auto end1 = std::chrono::high_resolution_clock::now(); 
    std::cout << "Elapsed = " << 
     std::chrono::duration_cast<std::chrono::milliseconds>(end1 - start).count() << 
     std::endl; 

    } 

    { 

    auto begin = std::chrono::high_resolution_clock::now(); 

    //new version 

    const long limit{40000000}; 
    vector<bool> k(limit-1,true); 

    //k[0] is the number 0 
    k[0]=false; k[1]=false; 

    auto sq = sqrt(limit) + 1; 

    //start at the number 2 
    for (int i=2;i<sq;i++)        
     {                
     if (k[i]==true)            
      {                
      for (int j=i+i;j<limit;j+=i)     
       {              
       k[j]=false; 
       } 
      } 
     } 


    vector <long long int> arr; 
    for (int i=0;i<limit-2;i++) 
     { 
     if (k[i]==true) 
      { 
      arr.push_back(i); 
      } 
     } 
    cout << arr.size() << endl ; 



    auto stop = std::chrono::high_resolution_clock::now(); 
    std::cout << "Elapsed = " << 
     std::chrono::duration_cast<std::chrono::milliseconds>(stop - begin).count() << 
     std::endl; 

    } 

デバッグモードで（ミリ秒単位で経過時間）の出力は、されています

2433654 
Elapsed = 5787 
2433654 
Elapsed = 2432 

の両方が同じ結果を持っている、第二には、はるかに高速です。ここで

は、（より少ないコードを必要とする）いくつかの素晴らしいC++の機能を使用して別のバージョンであり、そしてそれは、上述した第2のバージョンよりも約11％高速である：あなたの元のバージョンでは、あなたの3人にpush_backこと

auto begin = std::chrono::high_resolution_clock::now(); 

    const long limit{40000000}; 
    vector<int> k(limit-1,0); 

    //fill with sequence of integers 
    std::iota(k.begin(),k.end(),0); 

    //k[0] is the number 0 
    //integers reset to 0 are not prime 
    k[0]=0; k[1]=0; 

    auto sq = sqrt(limit) + 1; 

    //start at the number 2 
    for (int i=2;i<sq;i++)        
     {                
     if (k[i]) 
      {                
      for (int j=i+i;j<limit;j+=i)     
       {              
       k[j]=0; 
       } 
      } 
     } 

    auto results = std::remove(k.begin(),k.end(),0); 

    cout << results - k.begin() << endl ; 


    auto stop = std::chrono::high_resolution_clock::now(); 
    std::cout << "Elapsed = " << 
     std::chrono::duration_cast<std::chrono::milliseconds>(stop - begin).count() << 
     std::endl; 

    } 

注意現代の慣用句のこの使用は、vectorで動作しているときには、まったくpush_backを使用することはありません。

この例では、vectorはintです。これで、終了時に素数の実際の一覧が得られます。

出力：

2433654 
Elapsed = 2160 

これら上記のすべてのデバッグモード番号があります。リリースモードで

、あなたが実際の素数が終了しているものを気にしない場合は最高のは、boolsのベクターを用いて数値を使用して、上記第二と第三の技術を組み合わせたものです：

2433654 
Elapsed = 1098 
2433654 
Elapsed bool remove= 410 
2433654 
Elapsed = 779 

リリースモードでは、オリジナルのコードは5歳のノートパソコンで約1秒しかかかりませんので、デバッグモードで動作している可能性があります。

Answer 2

2つのことを変更することで、コンピュータでわずか10秒で動作するようになりました。まず、最適化を有効にしてコンパイルしなかったと思います。それは私のために10秒から1秒にそれを持って来ました。第2に、ベクトルcは不要である。コード内にc[i]がある場合は、i+2と置き換えることができます。これにより、2倍の速さで実行されます。

Answer 3

1. ベクターcを削除すると、不要になります。
2. 開始時に既知のサイズのベクトルkを作成します。 push_back()を呼び出すことによって、要素をベクトルに繰り返し追加することは、繰り返しのメモリの再割り当てやコピーを引き起こす可能性があるため、パフォーマンスの観点からは本当に悪い考えです。
3. http://primesieve.org/segmented_sieve.html - インスピレーションのためのセグメント化されたバージョン。
4. 2と3の倍数をスキップすることができます。link from code review
5. コンパイラ最適化フラグの設定に問題があるようです。おそらく、設定をデバッグからリリースに変更していない可能性があります。あなたのリリーススピードアップとデバッグワンの違いは何ですか？