对于vector效率的分析

Posted by wyj on March 10, 2019

本蒟蒻这几天因为std::vector的巨大时空常数吃了不少亏。所以在此进行一些分析。

我用vector的仅有的两个原因是与其他STL的高度兼容和range-based for的简洁语法。这是前向星无法具备的。

有一种广泛流传的错误观点认为vector的任意位置insert是\(O(\sqrt{n})\)的,实际上是线性的。实际测试表明,3e5次头部insert耗时4.077s(real time,下同),6e5次耗时16.060s。相比较而言,在1e5次插入时性能逊色于vector的__gnu_cxx::rope,插入1e6个数只需3.845s(rope在头部插入好像是\(O(1)\)的,只花了0.234s)。

vector的clear不能释放内存。resize也不行。我已经做过实验了。两种正确的做法:

第一种需要大括号,很丑陋:{vector<int> t;v.swap(t);}
第二种可以逗号,但是长:v.clear(),v.shrink_to_fit();

另外,vector的建立是相当耗时的。由于push_back会非常智障的频繁动态申请内存,建一棵1e6个点的随机树需要0.224s。对于CF1137C这样的5e6个点的图论题,光把分层图(及反图)建出来,1.368s已经过去,不被卡常就怪了。不开O2的话更是运行了3.018s。相比较,前向星使用了可以忽略不计的0.091s。这是因为vector分配了8814097次内存。

结论:图论题少用vector。

2019-03-16 UPD:

存在加速方法!

今天看了一个神仙的洛谷日报(将来时),学到了卡常方法。我早就知道可以手写allocator,之前我一直以为这是没有什么用的工程知识,现在却发现这是STL党的福音。将代码进行社会主义改造后如下:

char _[3<<25],*sp=_;
template<class T> struct alloc:allocator<T>{
//	alloc(){}
//	template<class T2> alloc(const alloc<T2> &a){}
//	template<class T2> alloc<T>& operator=(const alloc<T2>&a){return*this;}
	template<class T2> struct rebind{typedef alloc<T2> other;};
	inline T* allocate(size_t n){
		T* result=(T*)sp;sp+=n*sizeof(T);
		return result;
	}
	inline void deallocate(T* p,size_t n){}
};

这里有一个奇怪的情况:把任意几个成员函数删掉(甚至变成空struct),都可以编译成功并且输出正确结果,只不过是不能起到优化作用而已(还不如不写)。

关键是deallocate,allocate和rebind函数,对于速度提升缺一不可。暂且没有理解三个构造函数的作用(因为看起来删掉之后也一模一样)。

使用方法:vector<int,alloc<int>> v;

效果如下(一百万的树,建树+dfs两次刚好不T): 2019-03-16 19-33-12 的屏幕截图.png