关于使用STL的红黑树map还是hashmap的问题
最近在修改一个代理机server,增加url rewrite的功能,由于其单机的访问量很高,20000/s左右,对性能要求很高,所以在做url映射的时候,纠结在用map还是hashmap存储映射的问题上。
于是做了一个简单的测试,对与map和hashmap(我们用unordered_map),循环10000*24次,map大小是12(因为目前预估会配置的url个数是12左右)。
部分代码如下:
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include "markupstl.h"
#include <tr1/unordered_map>
#include <sys/time.h>
using namespace std;
#define hashmap std::tr1::unordered_map
#define CONFIG_FILE_PATH "./urlconfig.xml"
map<string,string> g_mapUrl;
hashmap<string,string> g_hashmapUrl;
struct timeval g_tpstart,g_tpend;
int timeuse;
gettimeofday(&g_tpstart,NULL);
for(int i = 0;i<10000;++i)
{
for(unsigned j = 0;j<g_vec.size();++j)
{
if (g_mapUrl.find(g_vec[j]) != g_mapUrl.end())
{
temp = g_mapUrl[g_vec[j]];
//cout<<temp<<endl;
}
}
}
gettimeofday(&g_tpend,NULL);
timeuse=1000000*(g_tpend.tv_sec-g_tpstart.tv_sec)+g_tpend.tv_usec-g_tpstart.tv_usec;
printf("map timeuse:%d\n",timeuse);
gettimeofday(&g_tpstart,NULL);
for(int i = 0;i<10000;++i)
{
for(unsigned j = 0;j<g_vec.size();++j)
{
if (g_hashmapUrl.find(g_vec[j]) != g_hashmapUrl.end())
{
temp = g_hashmapUrl[g_vec[j]];
//cout<<temp<<endl;
}
}
}
gettimeofday(&g_tpend,NULL);
timeuse=1000000*(g_tpend.tv_sec-g_tpstart.tv_sec)+g_tpend.tv_usec-g_tpstart.tv_usec;
printf("hashmap timeuse:%d\n",timeuse);
url映射是存在配置文件中的,12个左右:
<url clean="/user/info" ugly="/cgi-bin/xyoapp/xyoapp_get_userinfo.cgi" />
<url clean="/user/multi_info" ugly="/cgi-bin/xyoapp/xyoapp_multi_info.cgi" />
<url clean="/user/is_setup" ugly="/cgi-bin/xyoapp/xyoapp_get_issetuped.cgi" />
<url clean="/user/emotion" ugly="/cgi-bin/xyoapp/xyoapp_get_emotion.cgi" />
<url clean="/relation/is_friend" ugly="/cgi-bin/xyoapp/xyoapp_get_isrelation.cgi" />
<url clean="/relation/friends" ugly="/cgi-bin/xyoapp/xyoapp_get_relationinfo.cgi" />
<url clean="/network/classes" ugly="/cgi-bin/xyoapp/xyoapp_get_joinclass.cgi" />
<url clean="/pay/balance" ugly="/cgi-bin/xyoapp/xyoapp_pay_get.cgi" />
<url clean="/pay/pre_pay" ugly="/cgi-bin/xyoapp/xyoapp_pay_pay.cgi" />
<url clean="/pay/confirm" ugly="/cgi-bin/xyoapp/xyoapp_pay_confirm.cgi" />
<url clean="/pay/cancel" ugly="/cgi-bin/xyoapp/xyoapp_pay_cancel.cgi" />
<url clean="/pay/is_vip" ugly="/cgi-bin/xyoapp/xyoapp_pay_showvip.cgi" />
运行后得到的结果是:
map timeuse:392035
hashmap timeuse:480670
有点出乎意料,hashmap居然比map的红黑树方式还要慢一点的。
再测试一下,我把map的数据量调大,变成1000左右。再次运行:
map timeuse:1085809
hashmap timeuse:453852
这个时候,hashmap几乎比map快了一倍还要多,不过基于我目前map的大小只有12左右,所以用红黑树的map就足够了。
刚才又上网搜了一下红黑树,发现大学学的算法是忘记的一干二净了,抽时间得补习一下了。。。
附:源代码下载
建议继续学习:
- 红黑树并没有我们想象的那么难(上) (阅读:19719)
- 红黑树并没有我们想象的那么难(下) (阅读:14833)
- HashMap解决hash冲突的方法 (阅读:11258)
- 无锁HashMap的原理与实现 (阅读:5369)
- 萃取(traits)编程技术的介绍和应用 (阅读:5034)
- 红黑树学习笔记 (阅读:4362)
- 一个简单的stl中string的split函数 (阅读:3265)
- STL笔记之二叉查找树 (阅读:3061)
- 小趣闻:STL的三个版本 (阅读:2876)
- STL笔记之hashtable (阅读:2638)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:Dante 来源: Vimer
- 标签: hashmap STL 红黑树
- 发布时间:2010-08-31 20:21:14
- [46] 界面设计速成
- [40] 视觉调整-设计师 vs. 逻辑
- [40] Oracle MTS模式下 进程地址与会话信
- [38] IOS安全–浅谈关于IOS加固的几种方法
- [37] android 开发入门
- [36] 程序员技术练级攻略
- [36] 如何拿下简短的域名
- [35] 图书馆的世界纪录
- [35] 【社会化设计】自我(self)部分――欢迎区
- [32] 读书笔记-壹百度:百度十年千倍的29条法则