标题：map/set的效率
出处：Felix021
时间：Sun, 14 Jun 2009 15:28:47 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1651

内容：
算是续上篇文章吧。

上篇文章最后我有一个不是太好的总结（当然，在上一篇应该成立）：
引用
结论：在大多数情况下，我们可以迷信STL之父对效率的迷信。


我们知道vector和数组在基本操作上都是同一数量级的，而且事实上它们的常数也没有多少差别
所以我们可以放心地用vector来替换数组，不仅如此，他们在存储效率上，几乎也没有差别
一个简单的测试程序表明，存储1kw个整数，使用vector，整个程序消耗38.4MB空间，使用array，消耗38.2MB空间。

所以在这里我们可以放纵我们的迷信。

但是迷信也有限度的，就像上帝可以创造万物，但是不能创造自己。

然后进入本篇的主题：map/set的效率。

众所皆知，map/set底层数据结构是RB Tree，虽然不是真正的平衡树

但是其查找效率在统计上是比AVL等平衡树效率更高的，都能达到O(logN)的水平。Excellent。

于是我就迷信了，导致了自己对map的滥用，导致了很挫的结果。

究其原因，我忽略了那个确实很容易被忽略的东西，因为在提及复杂度的时候一般都不讲它。

——它就是传说中的那个常数。（我是不是很挫? =.=）

废话少说，数据说话：

map/set + 1,000,000个int的插入：
real  0m2.153s
user  0m1.812s
sys  0m0.056s

vector + 1,000,000个int的插入 + sort()：
real  0m0.581s
user  0m0.436s
sys  0m0.016s
改成堆排sort_heap()：
real  0m0.628s
user  0m0.492s
sys  0m0.016s

差别已经很明显了。

-----

然后再看看内存占用：

map: 19.4MB
vector: 4.1MB

so, hash + map用来构建hash table是我至今为止干过的最挫的事情之一了。——还不如用个vector。


Generated by Bo-blog 2.1.0