随机插入/缺失的综合载体与链接表基准 [英] Comprehensive vector vs linked list benchmark for randomized insertions/deletions
问题描述
所以我知道这个问题，以及其他处理SO的问题问题，但大多数处理数据结构的复杂性（只是复制在这里，链接这理论上有O（
我理解复杂性似乎表明，
注意：此问题的灵感来源于 Bjarne Stroustrup在Going Native 2012上的演讲45和46 ，他谈到了处理器缓存和参考地点的真实性帮助向量，但不是所有（或足够）与列表。问题：有一个很好的方法来测试这个使用CPU时间而不是墙上的时间，并获得一个体面的方式随机插入和删除元素，可以预先做，所以它不影响时间？
作为奖励，这将是很好的能够应用这两个任意的数据结构（说矢量和哈希映射或类似的东西），以找到真实世界性能在一些硬件。
我想如果我要测试这样的东西，我可能开始代码这个订单上的东西：
#include< list>
#include< vector>
#include< algorithm>
#include< deque>
#include< time.h>
#include< iostream>
#include< iterator>
静态const int size = 30000;
template< class T>
double insert（T& container）{
srand（1234）;
clock_t start = clock（）;
for（int i = 0; i
T :: iterator pos = std :: lower_bound（container.begin（），container.end（），value）;
container.insert（pos，value）;
}
//取消注释以验证正确插入（在小容器中）。
// std :: copy（container.begin（），container.end（），std :: ostream_iterator< int>（std :: cout，\t））;
return double（clock（） - start）/ CLOCKS_PER_SEC;
}
模板< class T>
double del（T& container）{
srand（1234）;
clock_t start = clock（）;
for（int i = 0; i
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
std :: cout<< 列表的插入时间：< insert（1）<< \\\
;
std :: cout<< 载体的插入时间：<插入（v） \\\
;
std :: cout<< deque的插入时间：<插入物（d） \\\
\\\
;
std :: cout<< 列表的删除时间：< del（1）<< '\\\
';
std :: cout<< 向量的删除时间：< del（v）< '\\\
';
std :: cout<< deque的删除时间：< del（d）< '\\\
';
return 0;
}
因为它使用 clock ，这应该给予处理器时间不是挂墙时间（虽然一些编译器，如MS VC ++得到错误）。它不尝试测量插入时间，而不是时间来找到插入点，因为1）将需要一些更多的工作和2）我仍然不能弄清楚它会完成什么。这肯定不是 100％严格，但考虑到我从中看到的差异，我会有点惊讶，看到与更仔细的测试有显着的区别。例如，对于MS VC ++，我得到：
列表的插入时间：6.598
向量的插入时间：1.377
deque的插入时间：1.484
列表的删除时间：6.348
向量的删除时间：0.114
deque的删除时间：0.82
使用gcc我可以：
列表的插入时间：5.272
向量的插入时间：0.125
deque的插入时间：0.125
列表的删除时间：4.259
向量的删除时间：0.109
deque的删除时间：0.109
因为你必须分别计算每次迭代。你需要比 clock （通常是）更精确的来产生有意义的结果（更多的顺序或读取时钟周期寄存器）。如果你认为合适 - 如上所述，我缺乏动机，因为我看不出这是一个明智的事情。如果你觉得合适，请随意修改。
So I am aware of this question, and others on SO that deal with issue, but most of those deal with the complexities of the data structures (just to copy here, linked this theoretically has O(
I understand the complexities would seem to indicate that a list would be better, but I am more concerned with the real world performance.
Note: This question was inspired by slides 45 and 46 of Bjarne Stroustrup's presentation at Going Native 2012 where he talks about how processor caching and locality of reference really help with vectors, but not at all (or enough) with lists.
Question: Is there a good way to test this using CPU time as opposed to wall time, and getting a decent way of "randomly" inserting and deleting elements that can be done beforehand so it does not influence the timings?
As a bonus, it would be nice to be able to apply this to two arbitrary data structures (say vector and hash maps or something like that) to find the "real world performance" on some hardware.
I guess if I were going to test something like this, I'd probably start with code something on this order:
#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;
}
Since it uses clock, this should give processor time not wall time (though some compilers such as MS VC++ get that wrong). It doesn't try to measure the time for insertion exclusive of time to find the insertion point, since 1) that would take a bit more work and 2) I still can't figure out what it would accomplish. It's certainly not 100% rigorous, but given the disparity I see from it, I'd be a bit surprised to see a significant difference from more careful testing. For example, with MS VC++, I get:
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
With gcc I get:
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
Factoring out the search time would be somewhat non-trivial because you'd have to time each iteration separately. You'd need something more precise than clock (usually is) to produce meaningful results from that (more on the order or reading a clock cycle register). Feel free to modify for that if you see fit -- as I mentioned above, I lack motivation because I can't see how it's a sensible thing to do.
这篇关于随机插入/缺失的综合载体与链接表基准的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
