注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

勇敢的劳尤条

 
 
 

日志

 
 

map<char*,int>和map<string,int>的效率对比?  

2013-12-17 10:52:26|  分类: 数据结构知识积累 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
在服务器开发过程中,关于用户信息缓存的设计一直是个问题。
保存多少数据量合适?用什么的数据结构?怎么样才能做到效率以及内存的平衡?这是一个过程。

之前做过好几个测试了。主要是针对set和hash_set。理论上来说,hash_set在效率上应该完败set,因为平均O(1)的查询时间,胜过O(lgN),但是测试结果并非完全如此。

首先,对于set<int>和hash_set<int>,结果确实一如预期,hash_set的插入和查询时间上完胜。
但是,对于set<string>和hash_set<string>,结果却让我大吃一惊。
因为set无论在插入还是查询上面,时间比hash_set居然要快得多。下面列出一组数据。
                                        插入180000条                    查询500000次
hash_set<string>              2325ms                                 2908ms     
set<string>                        713ms                                   702ms
注:博客最后附上测试代码。
我一直不能理解这里!!!只能勉强猜测:string的hash函数或许计算太耗时了!
另外一点,set对string要求比较小,只需要有“小于”函数即可,而hash对string要求较高,还需要“等于”函数。
这两者的选择上,主要考虑:查找速度,数据量,内存大小这三点。

测试完了set,于是我又测试了map,但是map<string>同样效率不高。更重要的一点是,经过一段时间查资料,慢慢发现string在使用上,效率确实没有那么高,至少针对我的需求来说,char*足够了。
所以下面继续测试map<char*,int>和map<string,int>在插入和存储效率的对比。
                                        插入100000条                    查询100000次
map<string,int>              119ms                                  89ms     
map<char*,int>               9ms                                      6ms
注:博客最后附上代码,这个测试结果并不能与上面的测试结果进行对比,因为用的是不同的数据内容,而且也没想过对比。因为map和set底层都是基于rb-tree实现的,原则上效率相当,只是用处不同而已。
从这个测试结果,我更加坚定了我的想法,如果char*完全能够满足我的需求,为什么一定要string呢?string移植性还不如
char*呢。
测试代码比较简陋,只为简单看看基本结果!
下面这篇博客,STL系列之九 探索hash_set,详细介绍了hash_set,还有许多链接,值得推荐!而且那里还给出了一个测试案例的代码。

第一个测试的代码
hash_set < string > hsUsername;
set< string > hsSet;
这两个对于插入和查询效率的对比。

#include<iostream>
#include<ctime>
#include<hash_set>
#include<set>
#include<string>
using namespace std;
namespace std
{
using namespace __gnu_cxx;
}
namespace __gnu_cxx
{
    template<> struct hash<const string>
    {
        size_t operator()(const string& s) const
        { return hash<const char*>()( s.c_str() ); } //__stl_hash_string
    };
    template<> struct hash<string>
    {
        size_t operator()(const string& s) const
        { return hash<const char*>()( s.c_str() ); }
    };
}

const int MAX=500000;
const int ArrY=4;
string a[MAX],query[MAX];
int main()
{
    hash_set < string > hsUsername;
    set< string > hsSet;
    char gch[62];
    for (int i = 0; i < 10; ++i) gch[i] = '0' + i;
    for (int i = 0; i < 26; ++i) gch[i + 10] = 'A' + i;
    for (int i = 0; i < 26; ++i) gch[i + 36] = 'a' + i;
    srand((unsigned int)time(NULL));
    char tmp[ArrY];
    for (int i = 0; i < MAX; ++i)
    {
        //a[i] = ( rand() * rand() )% (4 * MAX);
        int x = ( rand() * rand() )% MAX;
        for (int j = ArrY-1; j >= 0; --j)
        {
            tmp[j] = gch [x % 62];
            x/=62;
        }
        a[i]=string(tmp);
    }
    for (int i = 0; i < MAX; ++i)
    {
        //query[i] = ( rand() * rand() )% (4 * MAX);
        int x = ( rand() * rand() )% MAX;
        for (int j = ArrY-1; j >= 0; --j)
        {
            tmp[j] = gch[x % 62];
            x/=62;
        }
        query[i]=string(tmp);
    }
    clock_t clockBegin, clockEnd;

    clockBegin = clock();
    hsUsername.insert( a , a+MAX );
    clockEnd = clock();
    cout<<"insert time:"<<clockEnd-clockBegin<<"(ms)"<<endl;
    cout<<hsUsername.size()<<endl;

    clockBegin = clock();
    hsSet.insert( a , a+MAX );
    clockEnd = clock();
    cout<<"insert time:"<<clockEnd-clockBegin<<"(ms)"<<endl;

    int nfind = 0, nfindfail = 0;
    clockBegin = clock();
    for(int i = 0; i < MAX; ++i)
    {
        if(hsUsername.find( query[i] ) == hsUsername.end())++nfindfail;
        else ++nfind;
    }
    clockEnd = clock();
    cout<<"query time:"<<clockEnd-clockBegin<<"(ms)"<<endl;
    cout<<"find success:"<<nfind<<"\tfindfail:"<<nfindfail<<endl;

    nfind = 0, nfindfail = 0;
    clockBegin = clock();
    for(int i = 0; i < MAX; ++i)
    {
        if(hsSet.find( query[i] ) == hsSet.end())++nfindfail;
        else ++nfind;
    }
    clockEnd = clock();
    cout<<"query time:"<<clockEnd-clockBegin<<"(ms)"<<endl;
    cout<<"find success:"<<nfind<<"\tfindfail:"<<nfindfail<<endl;

    for(hash_set<string>::iterator it=hsUsername.begin();
        it!=hsUsername.end();++it)
    {
        string *pstr =*it;
    }
    return 0;
}


第二个测试代码
map<string,int> simap;
map<char*,int,cmp> cimap;
这两个对于插入和查询效率的对比。

#include<iostream>
#include<map>
#include<string.h>
#include<time.h>
using namespace std;
struct cmp
{
    bool operator()(const char *s1, const char *s2)
    {
        return strcmp(s1,s2)<0;
    }
};

int main()
{
    map<string,int> simap;
    map<char*,int,cmp> cimap;
    char sstr[32];
    clock_t cb,ce;
    cb=clock();
    for(int j=0;j<100000;++j)
    {
        int i=j;
        sstr[0]='0'+i%10;
        i/=10;
        sstr[1]='0'+i%10;
        i/=10;
        sstr[2]='0'+i;
        simap[sstr]=i;
    }
    ce=clock();
    cout<<ce-cb<<endl;

    cb=clock();
    for(int j=0;j<100000;++j)
    {
        sstr[0]='0'+7;
        sstr[1]='0'+8;
        sstr[2]='0'+9;
        simap.find(sstr);
    }
    ce=clock();
    cout<<ce-cb<<endl;

    cb=clock();
    for(int j=0;j<100000;++j)
    {
        int i=j;
        sstr[0]='0'+i%10;
        i/=10;
        sstr[1]='0'+i%10;
        i/=10;
        sstr[2]='0'+i;
        cimap[sstr]=i;
    }
    ce=clock();
    cout<<ce-cb<<endl;

    cb=clock();
    for(int j=0;j<100000;++j)
    {
        sstr[0]='0'+7;
        sstr[1]='0'+8;
        sstr[2]='0'+9;
        cimap.find(sstr);
    }
    ce=clock();
    cout<<ce-cb<<endl;
    return 0;
}


  评论这张
 
阅读(581)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017