下水道的井盖为什么是圆的？
map/set的效率
Jun
14
看过《STL之父访谈录》，了解了STL之父对效率的极度迷信，因而我对STL容器的效率也是很迷信的。
但是某一次和feli聊到vector的效率问题，他说，有时候在比赛的时候用vector会TLE，换成自己写的单链表就AC了。
可惜当时是在永和门口争论的，无法验证，后来某天想到这个问题，于是验证之：
1. vector和数组的效率对比：
对一个含有100,000,000个元素的int数组进行循环10遍的写入，测试结果(使用linux下的time命令统计)为：
Array:
real 0m3.801s
user 0m3.136s
sys 0m0.568s
Vector:
real 0m4.210s
user 0m3.548s
sys 0m0.520s
可以看出，vector和Array相比，至少在acm程序中，效率损失几乎是可以忽略的。
还需要声明一点，这里的vector是在运行时动态申请的空间，而array则是预分配的。
测试程序后附。
2. 单链表的效率和STL的list效率对比：
添加10,000,000个元素，测试结果为：
单链表:
real 0m0.836s
user 0m0.620s
sys 0m0.204s
list<int>:
real 0m1.202s
user 0m1.024s
sys 0m0.168s
可以看出来，完全没必要和vector对比的，接近两个数量级的差距阿。
单链表比STL的list快并不是因为STL效率损失，而是因为STL的list是一个双向链表，可能还有更多的底层细节（具体我就不了解了）。
---------------------
所以很显然的，vector比手写的单链表快。快很多。非常多。至于原因，我觉得主要有2：
1。链表是基于指针访问的，不仅需要更多的访存，而且cache命中率会比较低。
而vector的存储空间是连续的，在连续访问的情况下，命中率会高很多。
2。链表的内存是动态申请的，每一次都使用new/malloc从系统维护的堆中进行申请，效率很低。
当然，STL的list使用了优秀的allocator，但是效率仍然和vector无法比拟，所以说明第一条才是关键。
结论：在大多数情况下，我们可以迷信STL之父对效率的迷信。
--------------------
下附测试代码：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
但是某一次和feli聊到vector的效率问题，他说，有时候在比赛的时候用vector会TLE，换成自己写的单链表就AC了。
可惜当时是在永和门口争论的，无法验证，后来某天想到这个问题，于是验证之：
1. vector和数组的效率对比：
对一个含有100,000,000个元素的int数组进行循环10遍的写入，测试结果(使用linux下的time命令统计)为：
Array:
real 0m3.801s
user 0m3.136s
sys 0m0.568s
Vector:
real 0m4.210s
user 0m3.548s
sys 0m0.520s
可以看出，vector和Array相比，至少在acm程序中，效率损失几乎是可以忽略的。
还需要声明一点，这里的vector是在运行时动态申请的空间，而array则是预分配的。
测试程序后附。
2. 单链表的效率和STL的list效率对比：
添加10,000,000个元素，测试结果为：
单链表:
real 0m0.836s
user 0m0.620s
sys 0m0.204s
list<int>:
real 0m1.202s
user 0m1.024s
sys 0m0.168s
可以看出来，完全没必要和vector对比的，接近两个数量级的差距阿。
单链表比STL的list快并不是因为STL效率损失，而是因为STL的list是一个双向链表，可能还有更多的底层细节（具体我就不了解了）。
---------------------
所以很显然的，vector比手写的单链表快。快很多。非常多。至于原因，我觉得主要有2：
1。链表是基于指针访问的，不仅需要更多的访存，而且cache命中率会比较低。
而vector的存储空间是连续的，在连续访问的情况下，命中率会高很多。
2。链表的内存是动态申请的，每一次都使用new/malloc从系统维护的堆中进行申请，效率很低。
当然，STL的list使用了优秀的allocator，但是效率仍然和vector无法比拟，所以说明第一条才是关键。
结论：在大多数情况下，我们可以迷信STL之父对效率的迷信。
--------------------
下附测试代码：
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 100000000;
int d[maxn];
vector<int> e;
int main(){
int i, j;
if(1){ // 1是测试数组，0是测试vector
printf("Array: \n");
for(j = 0; j < 10; ++j){
for (i = 0; i < maxn; ++i){
d[i] = 0;
}
}
}else{
e.resize(maxn);
printf("Vector: \n");
vector<int>::iterator p;
for(j = 0; j < 10; ++j){
for(p = e.begin(); p != e.end(); ++p){
*p = 2;
}
}
}
return 0;
}
#include<vector>
using namespace std;
const int maxn = 100000000;
int d[maxn];
vector<int> e;
int main(){
int i, j;
if(1){ // 1是测试数组，0是测试vector
printf("Array: \n");
for(j = 0; j < 10; ++j){
for (i = 0; i < maxn; ++i){
d[i] = 0;
}
}
}else{
e.resize(maxn);
printf("Vector: \n");
vector<int>::iterator p;
for(j = 0; j < 10; ++j){
for(p = e.begin(); p != e.end(); ++p){
*p = 2;
}
}
}
return 0;
}
#include <iostream>
#include <list>
using namespace std;
struct node_t{
int data;
node_t * next;
};
struct linklist{
node_t *root;
linklist(){ root = NULL; }
void insert(int t){
node_t *p = new node_t;
p->data = t;
p->next = root;
root = p;
}
void iterate(){
node_t *p = root;
while(p != NULL){
p->data = 2;
p = p->next;
}
}
/* 其实注释掉这一段是很挫的事情，但是因为只是测试使用一次，所以留给OS来做吧，这样程序会快点 :D
~linklist(){
node_t *p = root;
while(root != NULL){
p = root;
root = p->next;
delete p;
}
}
*/
};
const int maxn = 10000000;
int main(){
if(1){ // 1测试单链表，2测试list<int>
linklist t;
int i;
for (i = 0; i < maxn; ++i){
t.insert(i);
}
//t.iterate(); //如果遍历的话，还要慢些
}else{
list<int> t;
int i;
for (i = 0; i < maxn; ++i){
t.push_back(i);
}
/* //如果遍历的话，还要慢些
for (list<int>::iterator p = t.begin(); p != t.end(); ++p){
*p = 2;
}
*/
}
return 0;
}
#include <list>
using namespace std;
struct node_t{
int data;
node_t * next;
};
struct linklist{
node_t *root;
linklist(){ root = NULL; }
void insert(int t){
node_t *p = new node_t;
p->data = t;
p->next = root;
root = p;
}
void iterate(){
node_t *p = root;
while(p != NULL){
p->data = 2;
p = p->next;
}
}
/* 其实注释掉这一段是很挫的事情，但是因为只是测试使用一次，所以留给OS来做吧，这样程序会快点 :D
~linklist(){
node_t *p = root;
while(root != NULL){
p = root;
root = p->next;
delete p;
}
}
*/
};
const int maxn = 10000000;
int main(){
if(1){ // 1测试单链表，2测试list<int>
linklist t;
int i;
for (i = 0; i < maxn; ++i){
t.insert(i);
}
//t.iterate(); //如果遍历的话，还要慢些
}else{
list<int> t;
int i;
for (i = 0; i < maxn; ++i){
t.push_back(i);
}
/* //如果遍历的话，还要慢些
for (list<int>::iterator p = t.begin(); p != t.end(); ++p){
*p = 2;
}
*/
}
return 0;
}
欢迎扫码关注：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
