技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 关于使用STL的红黑树map还是hashmap的问题

关于使用STL的红黑树map还是hashmap的问题

浏览:7922次  出处信息

最近在修改一个代理机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就足够了。

刚才又上网搜了一下红黑树,发现大学学的算法是忘记的一干二净了,抽时间得补习一下了。。。

附:源代码下载

建议继续学习:

  1. 红黑树并没有我们想象的那么难(上)    (阅读:19676)
  2. 红黑树并没有我们想象的那么难(下)    (阅读:14787)
  3. HashMap解决hash冲突的方法    (阅读:11227)
  4. 无锁HashMap的原理与实现    (阅读:5325)
  5. 萃取(traits)编程技术的介绍和应用    (阅读:5008)
  6. 红黑树学习笔记    (阅读:4329)
  7. 一个简单的stl中string的split函数    (阅读:3259)
  8. STL笔记之二叉查找树    (阅读:3029)
  9. 小趣闻:STL的三个版本    (阅读:2868)
  10. STL笔记之hashtable    (阅读:2603)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1