c++ - 用于随机插入/删除的综合 vector 与链表基准

Question

所以我知道this问题，以及其他处理问题的 SO，但其中大部分处理数据结构的复杂性(只是复制到这里，链接这个理论上有 O(

我理解复杂性似乎表明列表会更好，但我更关心现实世界的表现。

注意:这个问题的灵感来自 slides 45 and 46 of Bjarne Stroustrup's presentation at Going Native 2012他在其中谈到了处理器缓存和引用位置如何真正帮助 vector ，但对列表根本没有(或不够)帮助。

问题: 是否有一种使用 CPU 时间而不是墙时间来测试它的好方法，并获得一种“随机”插入和删除可以事先完成的元素的好方法，所以它确实如此不影响时间？

作为奖励，如果能够将其应用于两个任意数据结构(比如 vector 和 HashMap 或类似的东西)以在某些硬件上找到“真实世界的性能”，那就太好了。

Answer 1

我想如果我要测试这样的东西，我可能会按以下顺序开始编写代码:

#include <list>
#include <vector>
#include <algorithm>
#include <deque>
#include <time.h>
#include <iostream>
#include <iterator>

static const int size = 30000;

template <class T>
double insert(T &container) {
    srand(1234);
    clock_t start = clock();
    for (int i=0; i<size; ++i) {
        int value = rand();
        T::iterator pos = std::lower_bound(container.begin(), container.end(), value);
        container.insert(pos, value);
    }
// uncomment the following to verify correct insertion (in a small container).
//  std::copy(container.begin(), container.end(), std::ostream_iterator<int>(std::cout, "\t"));
    return double(clock()-start)/CLOCKS_PER_SEC;
}


template <class T>
double del(T &container) {
    srand(1234);
    clock_t start = clock();
    for (int i=0; i<size/2; ++i) {
        int value = rand();
        T::iterator pos = std::lower_bound(container.begin(), container.end(), value);
        container.erase(pos);
    }
    return double(clock()-start)/CLOCKS_PER_SEC;
}       

int main() { 
    std::list<int> l;
    std::vector<int> v;
    std::deque<int> d;

    std::cout << "Insertion time for list: " << insert(l) << "\n";
    std::cout << "Insertion time for vector: " << insert(v) << "\n";
    std::cout << "Insertion time for deque: " << insert(d) << "\n\n";

    std::cout << "Deletion time for list: " << del(l) << '\n';
    std::cout << "Deletion time for vector: " << del(v) << '\n';
    std::cout << "Deletion time for deque: " << del(d) << '\n';

    return 0;
}

因为它使用时钟，这应该给处理器时间而不是墙上时间(尽管一些编译器如 MS VC++ 弄错了)。它不会尝试测量插入时间(不包括找到插入点的时间)，因为 1) 这需要更多的工作，并且 2) 我仍然无法弄清楚它会完成什么。它当然不是 100% 严格，但考虑到我从中看到的差异，我会有点惊讶地发现与更仔细的测试有显着差异。例如，使用 MS VC++，我得到:

Insertion time for list: 6.598
Insertion time for vector: 1.377
Insertion time for deque: 1.484

Deletion time for list: 6.348
Deletion time for vector: 0.114
Deletion time for deque: 0.82

使用 gcc 我得到:

Insertion time for list: 5.272
Insertion time for vector: 0.125
Insertion time for deque: 0.125

Deletion time for list: 4.259
Deletion time for vector: 0.109
Deletion time for deque: 0.109

将搜索时间分解出来并非易事，因为您必须分别计算每次迭代的时间。您需要比 clock(通常是)更精确的东西才能从中产生有意义的结果(更多关于订单或读取时钟周期寄存器)。如果您认为合适，请随意修改 - 正如我上面提到的，我缺乏动力，因为我看不出这是一件明智的事情。