请选择 进入手机版 | 继续访问电脑版

赵耀的知识库

 找回密码
 立即注册
搜索
热搜: 报盘 状态 失败
查看: 10652|回复: 0

cpp的map和unordered_map和hash_map三个map的基准测试

[复制链接]

375

主题

381

帖子

2324

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
2324
发表于 2020-9-22 18:47:37 | 显示全部楼层 |阅读模式
map和undermap

map:
map内部实现了一个红黑树 所有元素都是有序的。


hash_map:






unordered_map:
内部实现了一个哈希表 其元素的排列顺序是无序的。


std::map 所有元素都是有序(红黑树)
tr1::unordered_map元素的排列顺序是无序的(哈希表)
测试一:O1编译
插入10000000次      
map类型插入int插入std::string全部查找int全部查找std::string
std::map10.8376 sec21.5493 sec5.74504 sec15.0929 sec
std::undermap4.28926 sec15.0095 sec1.13164 sec

8.01999 sec
tr1::undermap3.04517 sec13.7193 sec0.579665 sec5.88345 sec



测试一:O3编译
插入10000000次      
#include <map>
#include <ext/hash_map>
#include <unordered_map>
#include <tr1/unordered_map>
map类型插入insert遍历find内存占用
std::map5.16828 sec3.17102 sec470032kB
tr1::undermap1.17658 sec0.127977 sec453968kB
hash_map0.934131 sec0.141593 sec411888kB
std::undermap1.27186 sec0.157253 sec453976kB

g++ -O3 main.cpp -std=c++11 -o app

/**
比较map、hash_map和unordered_map的执行效率以及内存占用情况
**/

#include <sys/types.h>
#include <unistd.h>
#include <sys/time.h>   
#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <ext/hash_map>
//#include <unordered_map>
#include <tr1/unordered_map>
#include <string.h>

using namespace std;

using namespace __gnu_cxx;

using namespace std::tr1;

#define N 10000000  //分别测试N=100,000、N=1,000,000、N=10,000,000以及N=100,000,000

//分别定义MapKey=map<int,int>、hash_map<int,int>、unordered_map<int,int>
//typedef map<int,int> MapKey;          //采用map
//typedef hash_map<int,int> MapKey;     //采用hash_map
typedef unordered_map<int, int> MapKey;  //采用unordered_map


int GetPidMem(pid_t pid, string& memsize)
{
    char filename[1024];

    snprintf(filename, sizeof(filename), "/proc/%d/status", pid);

    ifstream fin;

    fin.open(filename, ios::in);
    if (!fin.is_open())
    {
        cout << "open " << filename << " error!" << endl;
        return (-1);
    }

    char buf[1024];
    char size[100];
    char unit[100];

    while (fin.getline(buf, sizeof(buf) - 1))
    {
        if (0 != strncmp(buf, "VmRSS:", 6))
            continue;

        sscanf(buf + 6, "%s%s", size, unit);

        memsize = string(size) + string(unit);
    }

    fin.close();

    return 0;
}

int main(int argc, char* argv[])
{
    struct timeval begin;

    struct timeval end;

    struct timeval end2;
    MapKey MyMap;


    gettimeofday(&begin, NULL);

    for (int i = 0; i < N; ++i)
    {
        //MyMap.insert(make_pair(std::to_string(i), i));
        MyMap.insert(make_pair(i, i));
    }
    gettimeofday(&end, NULL);

    cout << "insert N=" << N << ",cost=" << end.tv_sec - begin.tv_sec + float(end.tv_usec - begin.tv_usec) / 1000000 << " sec" << endl;

    for (int i = 0; i < N; ++i)
        //MyMap.find(std::to_string(i));
        MyMap.find(i);

    gettimeofday(&end2, NULL);

    cout << "foreach N=" << N << ",cost=" << end2.tv_sec - end.tv_sec + float(end2.tv_usec - end.tv_usec) / 1000000 << " sec" << endl;

    string memsize;

    GetPidMem(getpid(), memsize);

    cout << memsize << endl;

    return 0;
}


STL—map、hash_map、unordered_map
1.基本定义

  map底层是用红黑树实现的,查找时间复杂度是O(log(n));
  hash_map底层是用hash表存储的,查询时间复杂度是O(1);
  unordered_map和hash_map基本一样,只是unordered_map已经加到C++11标准(编译时添加编译选项:--std=c++11),而hash_map未加入在C++11标准中。
  由于map使用红黑树实现,所以是有序存储的,因此map的key需要定义operator<,而hash_map和unordered_map是基于hash无序存储的,因此只需要重载operator==。
2.hash_map、unordered_map

  hash_map基于哈希表,因此数据插入和查找的时间复杂度几乎是常数时间,而代价是消耗比较多的内存。底层实现上,使用一个下标范围比较大的数组来存储元素,形成很多的桶,利用hash函数对key进行映射到不同区域进行保存。
    插入操作:使用key通过hash函数得到hash值 -> 得到桶号(hash值对桶数求模) -> 存放key和value在桶内
    取值过程:使用key通过hash函数得到hash值 -> 得到桶号(hash值对桶数求模) -> 比较桶内元素与key是否相等 -> 取出相等纪录的value
  因此hash_map和用户相关的是:hash函数和比较函数,这两个参数刚好是我们在使用hash_map时需要指定的参数。如果每个桶内部只有一个元素,那么查找的时候只有一次比较,因此查询时间复杂度是O(1)。
在容器中不包含key值时,insert函数只要立刻插入新节点。但是当容器中元素增多,每个桶中的元素会增加,为了保证效率, hash_map会自动申请更大的内存,以生成更多的桶,因此在insert以后,以前的iterator有可能是不可用的。
  【1】hash_map桶的扩容机制
    扩容时需要满足两个条件:存放新值的时候当前hash_map所有元素的个数大于等于阈值;存放新值的时候当前存放数据发生hash碰撞。
    STL会默认指定初始桶大小为16,负载因子是0.75,因此阈值就是16*0.75 = 12,所以当新插入元素时,当前的元素个数超过12,并且发生了冲突,就会扩容hash桶。扩容的大小是给之前的数组翻倍。
    在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。 所以如果已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能,例如最多有1000个元素,则创建时:new HashMap(2048)(1024是不够的,要考虑负载因子:1024*0.75 = 768)。
    另外桶的大小为2的幂次方时,hash_map的效率最高。这是因为:正常的取index方法为hash%length,但是由于位运算比取余快,所以代码中实现为index = hash & (length - 1),所以只有length大小为2的次幂时:hash % length == hash & (length - 1)。
3.用法

  总体来说,hash_map 查找速度会比map快,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小, 因为hash函数计算也需要耗时,如果在元素达到一定数量级时同时要考虑效率,此时应该使用hash_map。如果对内存使用特别严格,需要程序尽可能少消耗内存,那么应该是用map,因为hash_map占用内存较多。






回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则