随机插入/删除的综合载体与链表基准

Question

所以我知道这个问题,而其他关于SO的问题涉及到问题,但大多数处理数据结构的复杂性(只是复制到这里,理论上将其与O连接起来(

我理解复杂性似乎表明列表会更好,但我更关注现实世界的表现.

注意:这个问题的灵感来自于Bjarne Stroustrup在2012年Going Native上的演示45和46,其中他讨论了处理器缓存和引用的位置如何真正有助于向量,但根本没有(或足够)列表.

问题:有没有一种很好的方法来测试这个使用CPU时间而不是墙上时间,并获得一种"随机"插入和删除可以事先完成的元素的体面方式,因此它不会影响时间？

作为奖励,能够将其应用于两个任意数据结构(例如矢量和哈希映射或类似的东西)以在某些硬件上找到"真实世界性能"将是很好的.

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

由于它使用clock,这应该给处理器时间而不是挂起时间(虽然一些编译器,如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(通常是)更精确的东西来产生有意义的结果(更多的是订单或读取时钟周期寄存器).如果你认为合适的话,请随意修改 - 正如我上面提到的,我缺乏动力因为我看不出它是一个明智的做法.