另一个向量vs动态分配的数组

Question

人们经常会发现,动态分配的数组与之间的性能差异很小std::vector.

以下是项目Euler测试问题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并且没有预先计算其最终大小.

这是阵列版本:

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编译器编译的,具有优化标志O2.我真的没有看到什么应该是最大的区别,因为移动语义(允许按值返回大矢量而不复制).

以下是结果,输入为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_count0 开头!从初始化角度和迭代角度来看,这都浪费了内存.你想要做的是:

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;
    }

你构造了一个max_prime初始化为true 的整数的向量...然后再将它们中的大多数赋值为true.你在这里做了两次初始化,而在数组实现中你只做了一次.你应该删除这个for循环.

我打赌如果你解决这两个问题 - 这会使两个算法相当 - 你会得到相同的性能.