std::map和stdext::hash_map效率问题

近期,接到一个项目,由于需要在程序运行中解析一部分数据,且该部分数据需要向后提供。
所以前同事在设计时使用了stdext::hash~map。
近期在优化该程序,需要将处理能力提高100%,我从IO,队列锁等方面改了一大通,现在效率才提高50%。
所以想问下经验较多的人,map和hash~map效率到底差距有多少(结合我的使用场景)。

1、每个map(hash~map)最多只有100个数据,键值为string
std::map
键值长度4~30个字符不等,且会存在汉语(会影响效率吗)
2、每个处理逻辑map均会重新构建,
两者插入效率是否差异较大。
3、查询效率,该部分自己已经写代码测试过。两者效率(vs2008+STLport)差异不大,查询10万次hash~map约少个1毫秒。(GetTicketCount());

由于现在想知道,但是手头没有电脑,没法测试,想问下大家具体的经验。最好是自己做过实验的。

0

3个回答

0

map是排序的红黑树,查找速度比hash表要慢一点。
不够你应该需要先看是不是时间性能主要处在map查找上。

0
oyljerry
oyljerry 回复coane: 先找出最大瓶颈的地方
4 年多之前 回复
coane
coane 理论上不是,因为需要存储的元素个数很少,最多O(ln100)的级别
4 年多之前 回复

用intel c++编译器编译下, 什么代码不改,都能比fcc快20%,比vc快30%,然后检测下热区,再调优下即可。

0
coane
coane 我g++编译还没使用优化
4 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
关于map,hash_map小数据量查询效率的问题
关于map>nMultimapnHash_map>nHash_multimapn对于数据量不大情况下的测试情况:n查询key值为4的情况下循环100万次得出的查询时间:nHash_map执行时间为868.575351秒nHash_multimap 执行时间892.441939秒nMap_vector执行时间:717.130047秒nMultimap执行时间为749.253617秒
B+Tree/Hash_Map/STL Map三种数据结构性能
Hash操作能根据散列值直接定位数据的存储地址,设计良好的hash表能在常数级时间下找到需要的数据,但是更适合于内存中的查找。nB+树是一种是一种树状的数据结构,适合做索引,对磁盘数据来说,索引查找是比较高效的nSTL_Map的内部实现是一颗红黑树,但是只是一颗在内存中建立二叉树树,不能用于磁盘操作,而其内存查找性能也比不上Hash查找。n因此对于内存中数据,查找性能较好的数据结构是Hash_Map
boost::unordered_map 和 std::map 的对比(包括速度和内存消耗)
背景:rn最近处理的单个文件,大概有13GB,数量条数约5000万。一次性读人到内存需要选择合适的数据结构对其进行存储。本文对比boost::unordered_map 和 std::maprnrn这两种数据结构在该使用情景下的效率。rn代码:rn#include "boost/unordered_map.hpp"n#include n#include n#include "time.h"nnus
C++ map和hash_map简单对比
C++ map 和 hash_map 对比rnmap的基本数据结构是平衡二叉树,hash_map的基础数据结构是hash_table哈希表,下面程序展示了向map和hash_map中插入数据消耗时间对比。rn数据量较小的时候可以选择map,数据量大、对插入查找效率要求高的时候选择hash_map。rnrn/**********************************************
map的insert和[]重载下标
std::pair<iterator,bool> insert( const value_type& value );insert会判断以K为键的是否存在,如果不存在,则进行正常的插入。如果存在,则插入失败。可以利用返回值来判断插入是否成功,代码如下:auto ite=test_map.insert(std::make_pair(K,V));nif(ite.second)n cout<<"插
c++中hash_table以及std::map应用案例
代码重点是hash_table,附加std::map与其做对比,实现的是一条sql语句:select c_nationkey, c_mktsegment, count(*), max(c_acctbal) from aaa_customer_1g group by c_nationkey, c_mktsegment order by c_nationkey, c_mktsegment
map和hash_map的区别
1、STL的map底层是用红黑树(RB Tree)实现的,查找时间复杂度是log(n),而hash_map底层是用hash表存储的,查询时间复杂度是O(1)2、hash_map比map查找速度更快。3、linux c的使用方法#include &amp;lt;map&amp;gt; //mapusing namespace std;//make_pair需要#include &amp;lt;hash_map&amp;gt;usi...
c++STL中的hash_map自定义类。
是的,hash_map是一个很方便的容器,有了STL确确实实给了C++developer很大方便,hash_map就是其中一种。他在数据少的时候,作用和基于RB-tree的map差不多,甚至不如,毕竟有hasher。但是在大量数据的时候,就很快捷了。我平时用hash_map都是用基本类型的,最多弄个string类,也是库里已经弄好了的。直接套模板就行。可是今天遇到一个问题就是当你需要把一个自定义类
C++ map 和 hash_map基本用法 遍历- 插入- find -释放 memory - 对象类型的操作 -remove_if 的替代方法
/***n * 练习map和 hash_map 的基本用法n * insert 插入n * map 遍历n * map findn * object 的成员在一定范围 的find remove_if() 的替代方法n * map erasen * map delete key-valuen * map modify datan * 交换 两个mapn * map vector 的memory 的...
std::map 操作符[] 编译提示 error C2512: 自定义类型 没有合适的默认构造函数可用
原因:map的value没有定义默认构造函数nnclass myTypen{npublic:nmyType(){a=10000;} //没有定义默认构造函数,std::map的operator[]将会编译报错nmyType(int a){this-&amp;gt;a = a;}nint a;n}n...nstd::map&amp;lt;int, myType&amp;gt; myMap;nmyMap.insert(pa...
HashMap的简单实现,具有线程安全
hashmap实现
C++中多个嵌套hash_map的合并运算
#include rn#include rnrnrnusing namespace std;rnrnrnhash_map>> DataMap;rnrnrnvoid Calc(hash_map>> SDataMap)rn{rn// 遍历hash_maprnhash_map>>::iterator it1 = SDataMap.begin();rnfor (it1;it1!=SDataMap.end(
STL 中 HashMap 解决冲突及增大空间的办法
STL 中 HashMap 解决冲突一般采用链表法,其特点是利用空间换时间,查找复杂度能达到常数级别。通常还有一种解决冲突的办法,开放地址法,分别有线性探测(Linear probing)、二次探测(Quadratic probing)、二次哈希(Double hashing)三种方式。nn参考链接:nnnhttps://blog.csdn.net/loveRooney/article/detai...
HashMap的clear()操作和new HashMap的时间效率比较
结论:看来分配内存都很耗时啊,也是用clear()比较快import java.util.*;n/*在一个smallCostBigFunction()中就需要一个preRoud的clear操作,n * 其中preRoud是全局变量,之所以用到全局变量,是因为smallCostBigFunction(),要将这个结果返回给dofire(),n * 但它同时要给一个Cost给dofire();n * 这
一个线程安全的std::map封装
#pragma oncennn#include n#include n#include n#include n#include nntemplatenclass concurrent_mapn{nprivate:n std::map the_map;n mutable boost::mutex the_mutex;n boost::condition_variable the_c
c++map效率实测
写个小程序对map的效率有个直观的认识,经过实际的测试发现map查询的速度比储存的速度要快一点。map通常是通过红黑树实现的,map的查找速度是log(n)级别。#include<cstdio>n#include<iostream>n#include<cmath>n#include<cstring>n#include<cstdlib>n#include<map>n#include<ctime>nus
关于std map的插入和删除
rn关于代码里map的删除,有一点困惑:rn在删除前用iterator保存位置,对map进行插入或删除后,iterator是否有效.rn看完标准后释然,直接上标准:23.1.2.8:The insert members shall not affect the validity of iterators and references to the container, and the erase ...
c++ hash_map用法总结
c++ STL库里有自定义的hash_map 方法,但是使用起来并不是那么方便rnhash_map主要的方法有rnfind(),insert()rn我结合官方API说明一下他们的用法rnrnrn一、需要特别注意的地方,rn1.头文件的引用rn2.如何插入一个键值对(参考一下代码)rn3.find()的返回值rn4.如何获取某一个key值相应的value值rnrn hm1_RcIter -> sec
C++哈希算法和map排序
7-1 词频统计(30 分)请编写程序,对一段英文文本,统计其中所有不同单词的个数,以及词频最大的前10%的单词。所谓“单词”,是指由不超过80个单词字符组成的连续字符串,但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线,其它字符均认为是单词分隔符。输入格式:输入给出一段非空文本,最后以符号#结尾。输入保证存在至少10个不同的单词。输出格式:在第一行...
使用map和hash_map的效率问题
1,选择map容器,是为了更快的从关键字查找到相关的对象。rn与使用list这样的线性表容器相比,一可以简化查找的算法,二可以使任意的关键字做索引,并与目标对象配对,优化查找算法。rn在C++的STL中map是使用树来做查找算法,这种算法差不多相当与list线性容器的折半查找的效率一样,都是 O(log2N),而list就没有map这样易定制和操作了。 rnrn2,相比map,hash_map使用...
关于Vector和Map查找效率的惊人的实际测试结果
最近在项目中有一种结构体数据需要存储,数据结构体如下nnnnntypedef mystructn{n int ID;n ......//其他的数据成员n double pinwei;n};nnn原本数据是由一个Vector存储的,Vector&lt;mystruct&gt; m_Vector;nnnn现在需要根据在m_Vector中的每一个结构体的ID来获得其对应的pinwe...
stl的map和hash_map简单例子
一:环境:linux g++nn二:代码:nnn#include &amp;lt;map&amp;gt;n#include &amp;lt;ext/hash_map&amp;gt;n#include &amp;lt;iostream&amp;gt;n#include &amp;lt;string.h&amp;gt;nnusing namespace std;nusing namespace __gnu_cxx;nnstruct hash_key_tn{n ...
c++中hash_map的使用
本人是极简主义者,直奔主题。nn概念及数据存储结构n    概念:hash_map是用来存储key-value键值对的集合,每一个键值对是一个Entry,这些Entry分散存储在一个数组中  ;n     核心技术:直接存址和解决冲突n     存储结构:分散的桶结构,每个桶节点中同时可以存放一个单链表(该链表使用头插法生成,主要是为了解决散列冲突      的问题)n说明一下hash_map在实...
C++ STL unordered_map和map的使用和性能分析
nunordered_map是C++ Boost库中的内容,这里的unordered翻译成“无序”。但它并不是完全的“无序”的概念,而是散列式的存储方式。nunordered库提供了两个散列映射类,unordered_map和unordered_multimap。n它们用散列表代替了二叉树的实现,模板参数多了散列计算函数,比较谓词使用equal_to&amp;lt;&amp;gt;。 n看到这里,我们就应该明白,...
STL中map和hash_map用法和区别
1. STL mapn1.1 为什么引入mapn考虑如何储存一系列key-value的键值对,最简单直观的是用一个数组或者链表保存。但是考虑下这样的插入、查找、删除效率,如果要高效,就需要把这些记录的键按照顺序排列,然后按照二分法查找,同时增加记录的时候也需要保持记录有序。我们如果自己去写需要考虑一系列因素,很麻烦对吧,所以STL中的map已经帮我们设计好了这一全套,我们只需要调用接口就好了。n1...
C++哈希表unordered_map,推荐使用。
在一个字符串(1rn解法1:使用数组,int hash[256];rn这题我竟然在想其他的歪点子,没想到第二次直接从数组0位置开始遍历(好蠢)(而不是哈希容器),不要动不动就想遍历哈希容器。rnclass Solution {npublic:n int FirstNotRepeatingChar(string str) {n if(str.empty()) return -1;
vector和map的效率简要比较
项目中要对一些数据结构进行存取,而项目本身对时间延时比较敏感,在使用vector还是map上着实纠结了一番,主要某些数据量比较小,才有此纠结。n而且想搞明白,到底大到什么数据量该用map?做了一些简单的测试,见下。nnn首先,不管是vector还是map,请尽量存取指针,否则在存取时会有拷贝带来不必要的时间损失。通常用int和string做key的场景比较普遍(我的项目即如此),能用int
检索速度最快的哈希算法和map
谁与争锋 对于c++程序来说 map的使用无处不在。影响程序性能的瓶颈也往往是map的性能。尤其在大数据情况下,以及业务关联紧密而无法实现数据分发和并行处理的情况。map的性能就成了最关键的技术。 比如:ip表、mac表,电话号码表、身份证号码表的查询、等等。 stl库的map采用二分查找,性能最差。Google的哈希map性能和内存目前是最优的。 我在电信行业和信息安全行业里的工作经历发现,目前网络上的哈希算法都在查询速度上远远无法满足日趋增长的网络大数据要求。因此产生了自己写算法的想法。 现在我把自己的算法初稿发布出来,用我在一家信息安全的公司打工时的应用场景进行测试。就是病毒库特征码的检索。
C++面试常见题目7_STL之map与unordered_map(红黑树VS哈希表)
map与unordered_mapnn相同:两者都是键-值对的集合,关联容器的一种。两者中的元素都是pair,同时拥有实值和键值。两者都不允许有两个相同的键值(实值可以相同)。两个的外部接口调用基本一致。n 不同:内部实现机理不同,即map内部实现了一个红黑树;unordered_map内部实现了一个哈希表。(两者的比较成为红黑树与哈希表的比较)。由于内部实现机理不同(底层实现)造成以下不同。nm...
map遍历的几种方式和效率问题
一、map遍历的效率nn先创建一个map,添加好数据:nnMap&amp;lt;String, String&amp;gt; map = new HashMap&amp;lt;&amp;gt;();nfor (int i = 0; i &amp;lt; 1000000; i++) {n map.put(i + &quot;&quot;, i + &quot;AA&quot;);n}nn1、keySet的for循环方式:nn//只获取keynpublic static v...
STL中的hash_map使用
主要分两部分来使用hash_map n1.针对 key = int char 等内置类型 n2.针对 key = 非内置类型部分源码全部来自于sgi-v2.03版 n都知道要使用hashtable必须有hash函数,由于STL内核提供了如下:内置的HashFcn:nstruct hash<char*>nstruct hash<const char*>nstruct hash<char> nstruc
严重不安全:STL map 使用map[key]==0判断key是否存在于map中
题目描述nn现在我们需要查出一些作弊的问答社区中的ID,作弊有两种:1.A回答了B的问题,同时B回答了A的问题。那么A和B都是作弊。2.作弊ID用户A和作弊ID用户B同时回答了C的问题,那么C也是作弊。已知每个用户的ID是一串数字,一个问题可能有多个人回答。nn输入描述:n每组数据第一行为总问题数N(N小于等于200000),第二行开始每行一个问题,第一个数字为提问人ID,第二个数字为回
map 与unordered_map的效率问题
问题描述:n项目开发过程中,为了方便,需要以string为key,实现key=>string value=>function的形式。然后查找key的效率对于服务器来说,是个至关重要的问题。n采用可能方式:n用stl提供的map,或者C++11新增加的unorder_mapn测试方案:n对map与unorder_map进行效率测试,采用大数据量的插入与查找n测试内容n       1.
Map遍历效率比较
1、由来     n      上次博客提到了Map的四种遍历方法,其中有的只是获取了key值或者是value值,但我们应该在什么时刻选择什么样的遍历方式呢,必须通过实践的比较才能看到效率。n        也看了很多文章,大家建议使用entrySet,认为entrySet对于大数据量的查找来说,速度更快,今天我们就通过下面采用不同方法遍历key+value,key,value不同情景下的差异
C++有序map和无序unordered_map性能测试对比
概述nn简单对比map和unordered_map的性能。 nmap内部是红黑树,在插入元素时会自动排序,而无序容器unordered_map内部是散列表,通过哈希而不是排序来快速操作元素,使得效率更高。当你不需要排序时选择unordered_map的效率更高。nn测试范例nn测试代码nnnn#include &amp;lt;iostream&amp;gt;n#include &amp;lt;string&amp;gt;n#in...
一个与map下标操作有关的编译错误(花了5分钟才找到原因)
来, 看程序:rn#include n#include n#include nusing namespace std;nnclass An{npublic:n map m_map; n};nnvoid test(const A &a)n{n string s = a.m_map["hello"];n cout << s << endl;n}nnint main()n{n A a;n a.m_map
c++线程安全的map
参考了 《c++并发编程实战》这本书上的代码写了一个线程安全可以并发的map/*n * threadsafe_map.cppn *n * Created on: May 11, 2018n * Author: clh01sn * 线程安全的查找表n * 通过boost的shared_mutex实现读写锁n * 假设有一定数量的桶,每一个键都有一个桶n * ...
C++中 直接调用、函数指针、std::function效率对比
[size=large]C++中 直接调用、函数指针、std::function效率对比rnrn调用次数:10亿次rnCPU: i7 860 (主频2.8GHz)rn[color=red]测试结果:[/color] 函数指针要比直接调用慢2s左右;std::function 要比函数指针慢2s左右rnrn貌似std::function调用时多了一句if语句的判断,用于测试是否绑定了函数。rnr...
stl map find使用不当导致的低概率core dump问题的定位
最近呢, 收到低概率core dump告警, 不频繁, 但挺恼人, 那就展开定位呗。再低概率的core, 在亿万请求下, 必然会发生。nnn       这么搞起:n       1. 上外网core dump的机器一看, 没有core文件了, 于是从backup目录找到了备份的coren       2. 看了一下core文件的大小, 太小, 无法定位, 这肯定是被截断了。
error C2039: “bad_alloc”: 不是“std”的成员
error C2039: “bad_alloc”: 不是“std”的成员nerror C3861: “bad_alloc”: 找不到标识符nn解决方法:nn#include &lt;exception&gt;n
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 java map 学习 python3.5教程map