C++優化此算法

Question

看了一些Terence Tao的視頻之後，我想嘗試將算法應用到C++代碼中，以查找所有素數達到n的數字。在我的第一個版本中，我測試了每個從2到n的整數，看看它們是否可以被2到sqrt（n）中的任何一個整除，然後我在52秒內找到了1-10,000,000之間的素數。我試圖優化程序並實施我現在知道的Eratosthenes篩選，我認爲這項任務將比51秒快得多，但可悲的是，情況並非如此。即使達到1,000,000也需要花費相當長的時間（雖然沒有時間）

#include <iostream> 
#include <vector> 
using namespace std; 

void main() 
{ 
    vector<int> tosieve = {};   
    for (int i = 2; i < 1000001; i++) 
    {          
     tosieve.push_back(i);    
    }          
     for (int j = 0; j < tosieve.size(); j++) 
     { 
      for (int k = j + 1; k < tosieve.size(); k++) 
      { 
       if (tosieve[k] % tosieve[j] == 0) 
       { 
        tosieve.erase(tosieve.begin() + k); 
       } 
      } 
     } 
    //for (int f = 0; f < tosieve.size(); f++) 
    //{ 
    // cout << (tosieve[f]) << endl; 
    //} 
    cout << (tosieve.size()) << endl; 
    system("pause"); 
} 

它是重複引用的向量還是什麼？爲什麼這麼慢？即使我完全忽略了某些東西（可能是，完全初學者：I），我認爲用這種可怕的低效率方法找到2到1,000,000的素數會比我從2到10,000,000找到它們的原始方式更快。

希望有人對此有明確的答案 - 希望在使用大量遞歸優化程序時，我可以使用將來收集的任何知識。

Answer 1

大部分vector操作，包括erase()都具有O(n)線性時間複雜度。

既然你有大小10^6的兩個循環，和大小10^6的vector，你的算法執行到10^18操作。

針對如此大的N的Qubic算法將花費大量時間。
N = 10^6對於二次算法來說足夠大。

請仔細閱讀關於Sieve of Eratosthenes。全搜索和Eratosthenes算法同時使用的事實意味着你已經完成了第二個錯誤。

Answer 2

問題是'擦除'會將向量中的每個元素向下移動一個，這意味着它是O（n）操作。

有三種可替換的選擇：

1）只要標示爲刪除的元素爲 '空'（使它們0，例如）。這意味着未來的傳球必須經過那些空位，但那並不昂貴。

2）製作一個新的矢量，並將push_back新的值寫入其中。

3）使用std :: remove_if：這會將元素向下移動，但是在一次傳遞中這樣做會更有效。如果你使用std :: remove_if，那麼你將不得不記住它不會調整矢量本身的大小。

Answer 3

我看到這裏有兩個問題performanse：

首先，push_back()將不得不在一段時間後重新分配的動態內存塊。使用reserve()：

vector<int> tosieve = {}; 
tosieve.resreve(1000001);  
for (int i = 2; i < 1000001; i++) 
{          
    tosieve.push_back(i);    
} 

二erase()必須移動你嘗試刪除一個後面的所有元素。您可以設置元素爲0，而不是做了到底（未經測試的代碼）的矢量運行：

for (auto& x : tosieve) { 
    for (auto y = tosieve.begin(); *y < x; ++y) // this check works only in 
               // the case of an ordered vector 
     if (y != 0 && x % y == 0) x = 0; 
} 
{ // this block will make sure, that sieved will be released afterwards 
    auto sieved = vector<int>{}; 
    for(auto x : tosieve) 
     sieved.push_back(x); 
    swap(tosieve, sieved); 
} // the large memory block is released now, just keep the sieved elements. 

考慮使用標準算法，而不是手寫循環。他們幫助你陳述你的意圖。在這種情況下我看到std::transform()爲篩，std::any_of()的用於內循環，std::generate_n()外環用於填充tosieve在開始和std::copy_if()用於填充sieved（未測試的代碼）：

vector<int> tosieve = {}; 
tosieve.resreve(1000001); 
generate_n(back_inserter(tosieve), 1000001, []() -> int { 
    static int i = 2; return i++; 
}); 

transform(begin(tosieve), end(tosieve), begin(tosieve), [](int i) -> int { 
    return any_of(begin(tosieve), begin(tosieve) + i - 2, 
        [&i](int j) -> bool { 
         return j != 0 && i % j == 0; 
        }) ? 0 : i; 
}); 
swap(tosieve, [&tosieve]() -> vector<int> { 
    auto sieved = vector<int>{}; 
    copy_if(begin(tosieve), end(tosieve), back_inserter(sieved), 
      [](int i) -> bool { return i != 0; }); 
    return sieved; 
}); 

編輯：

到弄完

還有一種方法：

vector<int> tosieve = {}; 
tosieve.resreve(1000001); 
generate_n(back_inserter(tosieve), 1000001, []() -> int { 
    static int i = 2; return i++; 
}); 
swap(tosieve, [&tosieve]() -> vector<int> { 
    auto sieved = vector<int>{}; 
    copy_if(begin(tosieve), end(tosieve), back_inserter(sieved), 
      [](int i) -> bool { 
       return !any_of(begin(tosieve), begin(tosieve) + i - 2, 
           [&i](int j) -> bool { 
            return i % j == 0; 
           }); 
      }); 
    return sieved; 
}); 

現在不是標記元素，W e之後不想複製，但只是直接複製元素，我們要複製。這不僅比上述建議更快，而且更好地說明了意圖。