Jun 14

map/set的效率 不指定

felix021 @ 2009-6-14 15:28 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(9900) | Via 本站原创 | |
算是续上篇文章吧。

上篇文章最后我有一个不是太好的总结(当然,在上一篇应该成立):
引用
结论:在大多数情况下,我们可以迷信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。



欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
xenplus Email Homepage
2009-6-14 22:05
最后一句。。。
felix021 回复于 2009-6-14 22:49
嗯。我是sx。。。
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]