另一个向量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循环。

我敢打赌，如果你解决了这两个问题 - 这会使两种算法具有可比性 - 你会得到相同的性能。