| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 11027 人关注过本帖
标题:STL效率初探(关键代码慎用STL)
只看楼主 加入收藏
jalor
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-12-15
  问题点数:0  回复次数:9   
STL效率初探(关键代码慎用STL)

想在工程里使用STL,但一直怀疑STL的效率,所以作了一下简单的测试,结果很让我吃惊。

测试方法:
用std::map与自己实现的CHashMap进行比较,分别插入并查询10000个键值

结果:
Release编译 Debug编译
std::map耗时 CHashMap耗时 std::map耗时 CHashMap耗时
插入10000个键值 0.018923秒 0.000421秒 0.161889秒 0.001955秒
查询10000个键值 0.001435秒 0.000233秒 0.061445秒 0.001808秒

结论:
在Release编译下,std::map在插入键值时速度比CHashMap慢了50倍,查询则慢了7倍!开始我很怀疑这个数据,但重复测试多次后,结果仍然一样。我又将std::map改为std::hash_map,结果还在一样(有细微差别,可忽略)。
以前看过很多文章,均建议使用STL,并且不要企图超越STL,我想这些建议应该是针对STL的通用性、与平台无关性,但就效率而言,STL并非最佳选择!
如果工程中的关键代码对效率要求极高,我觉得在这种地方要慎用STL。初学者不能被大量的STL赞歌所误导了,如果对某一模块的效率没有把握,最好的方法就是做测试,用数据说话。

另外:
我也是刚开始用STL,不知以上对std::map、std::hash_map的测试是否得当,请各位大侠不赐教。致少有一点我现在是迷惑的:std::map/std::hash_map不需要初始化容器的大小,我想它的内部实现是根据插入键值的多少自动分配容器大小,这势必会影响效率。我试着先往std::map/std::hash_map里插入10000个键值,然后清空,我认为这时它应该已分配敢足够的容器,然后再去测试插入10000的键值的时间,结果耗时依然不变!这就有点奇怪了!为什么std::map/std::hash_map的插入操作这么慢??

[此贴子已经被作者于2006-12-15 11:13:29编辑过]

搜索更多相关主题的帖子: STL 效率 std 初探 关键 
2006-12-15 11:10
song4
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:38
帖 子:1533
专家分:4
注 册:2006-3-25
  得分:0 
我估计里面是用动态数组编的
STL,可能效率在解决LZ个别问题确实不好
但现在大多数是在稳定的基础上求效率
当然,关键代码可以考虑自己写
只要以后都是你自己修改

嵌入式 ARM 单片机 驱动 RT操作系统 J2ME LINUX  Symbian C C++ 数据结构 JAVA Oracle 设计模式 软件工程 JSP
2006-12-15 16:20
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
  得分:0 
std::map/s其实就是链表的二叉平衡排序树,按道理,跟链表一样,一开始不需要预留空间,只有vector才要,因为重新分配内存的时候,会另迭代器失效,map会另迭代器失效的可能性只有是删除的时候.不知道你的chashmap是怎样实际做出来的,并且你是怎样用map来插入数据,顺便提醒一下 如果用map的[]符号来插入,是会慢一点的,最好用insert,估计你那个chashmap也是差不多用类似红黑树那个些来实作出来,而且最重要的是 map可以自定义排序准则.可以自定义内存适配器,要想map的速度够快,就要自己定义好这些东西.因为STL是由两个数据结构的专家来写的,在分配内存的方面,都是自己写的,并不是就这样new出来就完事了

[此贴子已经被作者于2006-12-19 17:43:18编辑过]


c++/C + 汇编 = 天下无敌
2006-12-19 17:37
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
  得分:0 
想客观的评价这些,要楼住提供一下代码,当然,那个CHASHMAP如果不想提供,可以用DLL的形式,然后给出main函数,看看楼主是怎样测的,不过不排除楼主的算法比STL优秀,不过如果STL的空间分配那部分是自己写的话,应该就不会差不到哪里去了,说实话,在实际开发中,我是很喜欢用STL的,因为它稳定

c++/C + 汇编 = 天下无敌
2006-12-19 18:06
zsyddl
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2008-8-28
  得分:0 
叮叮咚咚叮叮咚咚叮叮咚咚
2008-08-28 16:39
zsyddl
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2008-8-28
  得分:0 
今天因为公司的 东东使用到 hash,关心效率问题,在网上搜索,发现该贴。
对楼主的结果非常惊异,所以自己也动手测试了一把。以下 是测试的结论描述

对于网上有人对 stl hashmap的质疑,我觉得大师们的代码不可能是所说的那么烂吧。我自己也做了测试

。hash_map<string, int>, 使用 [] 进行查找和插入。电脑配置, 奔腾2.4 G 1G 内存
分别插入 10000, 100000, 200000, 300000,。。。。2000000 (200 万)。
初始化时间,这个就不详细列表了,逐渐增长,到200万是9秒多。
hash的优势是查找,测试结果,查询时间 基本都是在0.000044-0.000090之间,也就是 几十微妙。
同一个程序多次运行 稍微有变化,这个 应该是和计算机运行其他程序有关系。极少数出现过几十毫秒的

情况。这个应该是特殊情况。
从情况来看,人做的 10000次查询的毫秒级。而只是几十微妙,比楼主的hash几百微妙快 5倍

电脑硬件对比:
插入10000 个记录,楼上使用 0.018923毫秒,而我的使用 0.044065 说明 他的机器应该比我的快不少。
2008-08-29 10:06
jalor
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-12-15
  得分:0 
没想到还有朋友回这个贴子!
zsyddl的测试结果有些地方我看得不是很理解,比如“基本都是在0.000044-0.000090之间”,是单次还是10000次?
我今天又测了一下(硬件:3G Hz,512M RAM)
提准备好10000个键值对,做10000次插入,再做10000次查询,结果如下:
CHashMap插入:1.800000 毫秒
CHashMap查询:1.700000 毫秒

std::hash_map插入:42.100000 毫秒
std::hash_map查询:7.000000 毫秒

std::map插入:33.500000 毫秒
std::map查询:12.100000 毫秒

与我06年测的结果有出入,可能测试环境还是变了,不过明显的是STL的hash_map、map的效率是有问题
2008-11-24 14:28
zsyddl
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2008-8-28
  得分:0 
今天再次做了测试
vs2003 debug 和release 下面 效率相差将近1000*1000倍
测试了 map 和hashmap 在1000*100 的 数据中 最后结果 两者差不多。
对每个 值做查询,将时间总和求平均,即为 平均每次查询的时间
key int,value int
但是效率相当高
debug:
Test Stl effic, 100*1000
Test Map , total time : 0.330652871229807, aver time: 0.000003306528712 Second
Test Hash, total time: 0.215916911590558, aver time: 0.000002159169116 second
test finish
release
Test Stl effic, 100*1000
Test Map , total time : 0.000000219548047, aver time: 0.000000000002195 Second
Test Hash, total time: 0.000000216540539, aver time: 0.000000000002165 second
test finish

当然 大家都知道针对特定应用编写 hash 或者map 是可以比 stl 的高,但是 必须是特定应用。
要达到 stl 一样的通用,对所有情况保证效率一样高,99.9%程序员都不可能的。
2010-11-26 12:55
快速回复:STL效率初探(关键代码慎用STL)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.055017 second(s), 7 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved