另一個向量vs動態分配數組

Question

人們經常會讀到動態分配數組和std::vector之間幾乎沒有性能差異。

這裏有兩個版本的項目歐拉測試的問題10有兩個版本：

與std::vector：

const __int64 sum_of_primes_below_vectorversion(int max) 
{ 
     auto primes = new_primes_vector(max); 
     __int64 sum = 0; 
     for (auto p : primes) { 
       sum += p; 
     } 
     return sum; 
} 

const std::vector<int> new_primes_vector(__int32 max_prime) 
{ 
     std::vector<bool> is_prime(max_prime, true); 
     is_prime[0] = is_prime[1] = false; 
     for (auto i = 2; i < max_prime; i++) { 
       is_prime[i] = true; 
     } 
     for (auto i = 1; i < max_prime; i++) { 
       if (is_prime[i]) { 
         auto max_j = max_prime/i; 
         for (auto j = i; j < max_j; j++) { 
           is_prime[j * i] = false; 
         } 
       } 
     } 
     auto primes_count = 0; 
     for (auto i = 0; i < max_prime; i++) { 
       if (is_prime[i]) { 
         primes_count++; 
       } 
     } 

     std::vector<int> primes(primes_count, 0); 
     for (auto i = 0; i < max_prime; i++) { 
       if (is_prime[i]) { 
         primes.push_back(i); 
       } 
     } 
     return primes; 
} 

請注意，我還測試版本的版本與調用默認的構造函數std::vector並且沒有其最終大小的預計算。

這裏是數組版本：與優化標誌O2

const __int64 sum_of_primes_below_carrayversion(int max) 
{ 
     auto p_length = (int*)malloc(sizeof(int)); 
     auto primes = new_primes_array(max, p_length); 
     auto last_index = *p_length - 1; 

     __int64 sum = 0; 
     for (int i = 0; i < last_index; i++) { 
       sum += primes[i]; 
     } 

     free((__int32*)(primes)); 
     free(p_length); 
     return sum; 
} 


const __int32* new_primes_array(__int32 max_prime, int* p_primes_count) 
{ 
     auto is_prime = (bool*)malloc(max_prime * sizeof(bool)); 
     is_prime[0] = false; 
     is_prime[1] = false; 
     for (auto i = 2; i < max_prime; i++) { 
       is_prime[i] = true; 
     } 
     for (auto i = 1; i < max_prime; i++) { 
       if (is_prime[i]) { 
         auto max_j = max_prime/i; 
         for (auto j = i; j < max_j; j++) { 
           is_prime[j * i] = false; 
         } 
       } 
     } 

     auto primes_count = 0; 
     for (auto i = 0; i < max_prime; i++) { 
       if (is_prime[i]) { 
         primes_count++; 
       } 
     } 
     *p_primes_count = primes_count; 

     int* primes = (int*)malloc(*p_primes_count * sizeof(__int32)); 
     int index_primes = 0; 
     for (auto i = 0; i < max_prime; i++) { 
       if (is_prime[i]) { 
         primes[index_primes] = i; 
         index_primes++; 
       } 
     } 
     free(is_prime); 
     return primes; 
} 

這是編譯與MVS2013編譯器。 由於移動語義（允許通過值複製大矢量而不需要複製），我真的不知道應該有什麼重大區別。

下面是結果，與2E6的輸入：

C array version 
avg= 0.0438 
std= 0.00928224 
vector version 
avg= 0.0625 
std= 0.0005 
vector version (no realloc) 
avg= 0.0687 
std= 0.00781089 

的統計數據是在10次試驗。 我認爲這裏有很多不同之處。是否因爲我的代碼中的某些內容需要改進？

編輯：我的代碼（和其他改進）修正後，這裏是我的新成果：

C array version 
avg= 0.0344 
std= 0.00631189 
vector version 
avg= 0.0343 
std= 0.00611637 
vector version (no realloc) 
avg= 0.0469 
std= 0.00997447 

這證實了不存在的std::vector處罰比較C數組（這應該避免重新分配）。

Answer 1

向量和動態數組之間不應該存在性能差異，因爲向量是是動態數組。

你的代碼中的性能差異來自於你實際上在向量和數組版本之間做了不同的事情。例如：

std::vector<int> primes(primes_count, 0); 
    for (auto i = 0; i < max_prime; i++) { 
      if (is_prime[i]) { 
        primes.push_back(i); 
      } 
    } 
    return primes; 

這產生大小primes_count的向量，全部初始化爲0，然後推回一堆素數的到其上。但它仍然以primes_count 0開頭！所以從初始化角度和迭代角度都浪費了內存。你想要做的是：

std::vector<int> primes; 
primes.reserve(primes_count); 
// same push_back loop 
return primes; 

沿着同樣的路線，這塊;

std::vector<int> is_prime(max_prime, true); 
    is_prime[0] = is_prime[1] = false; 
    for (auto i = 2; i < max_prime; i++) { 
      is_prime[i] = true; 
    } 

您構建的初始化爲true max_prime整數向量...然後再次分配大多爲true。你在這裏做了兩次初始化，而在數組實現中你只做了一次。你應該刪除這個for循環。

我敢打賭，如果你解決了這兩個問題 - 這會使兩種算法具有可比性 - 你會得到相同的性能。