colorful

zc qq:1337220912

 

std::map查询效率优化

0.现状,数据是个xml文件,每个节点对应的结构体有10个成员变量,共有2000多条数据,用的std::map<string, struct>来保存,用map的find函数进行搜索时的效率极

 

其低下,循环搜索30条数据竟然要20s+,搓死。

 

1.为什么这么慢?

最初怀疑是std::map的效率问题,正考虑是否使用std::hast_map来替换,于是了解下两者之间的差别:

std::map是个自平衡的红黑树,他的效率是平均的

hash_map的是一个hash表,只要你的hash算法足够唯一,你的效率可以达到O(1)

 

翻书时大牛就在旁边,就问了他,把情况和他一说。他立刻点名:

用hash_map的效率确实会比map的高,但你的数据才2000多,两者在这里数量级上的效率差异应该很小。主要的问题应该在于你的map,你的map的value不是一个指针

 

,而是一个大结构体,这会导致搜索时的内存频繁被交换出去,因而导致效率低下。

 

2.按照大牛的建议,修改,测试,消耗的时间由原来的20s+变成了0

posted on 2012-07-21 22:14 多彩人生 阅读(4511) 评论(1)  编辑 收藏 引用

评论

# re: std::map查询效率优化 2014-05-05 10:09 coderchen

good  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(3)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜