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

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

附:源代码下载

暂无相关产品

6则回应给“关于使用STL的红黑树map还是hashmap的问题”

  1. egmkang说道:

    map!
    map是标准库容器,haspmap貌似不是.标准库容器都能经得起时间的推敲.
    之前有看到过,选择hashmap无非就是为了性能,但是map在几十万之内,性能好像还是很好的,不必hashmap差.以前看到文章有比较

    [回复]

  2. Heiher说道:

    学习了,我也应该认真学习一下算法了。

    [回复]

  3. muzimin说道:

    如果追求效率可以考虑trie树。比较适合字符串查找。

    [回复]

  4. 故事大王说道:

    话说,看到了 rewrite,不自觉的想到了apache之类的服务器URL的rewrite……其实成为URL映射更准确一些。

    另外,红黑树、平衡树、B+树之类的数据结构,已经感觉很遥远了。。。

    [回复]

    Dante 回复:

    我看到这些数据结构也是头疼的很。。。

    [回复]

  5. gamis haramain说道:

    excellent issues altogether, you simply won a brand new reader.

    What would you recommend in regards to your put up that you simply made a few days ago?
    Any certain?

    [回复]

发表评论