返回 登录
0

C++性能系列:map的使用误区

代码逻辑的实现需要键值对的时候我们喜欢偷懒,声明了不少map类型的局部变量,完全没有意识到map的真正用途。map是平衡二叉树,适用于快速检索。由于二叉平衡树插入机制以及内存分配的原因,它不适合频繁的内存操作,包括声明map对象、插入数据、删除数据。正确的用法是首先把所有的数据加工处理准备好,然后交给map存储,以便检索。C++11新的C++标准库加入了一个名为unordered_map的类型库,字面意义像是不排序,实际上它也不适合用作局部变量。下面测试代码一起进行压力测试看看。

#include <iostream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <memory>
#include <ctime>

using namespace std;
#define MAP_STRESSING 512
#define ARRAY_STRESSING 8096


typedef struct 
{
    int age;
    char sex;
    int a1;
    int a2;
    int a3;
    int a4;
    int a5;
    int a6;
    int a7;
    int a8;
}student_t,*pstudent_t;

typedef struct 
{
    int id;
    student_t students[ARRAY_STRESSING];
}school_t,*pschool_t;

void test_map();
void test_unordered_map();
void test_array_index();
void test_array_pointer();
void test_array_reference();

int main()
{
    clock_t time1=clock();
    clock_t time2=0;
    cout.setf(ios::fixed);
    cout<<"map测试:开始。"<<endl;
    test_map();
    time2=clock();
    cout<<"map测试:"<<right<<setw(8)<<time2-time1<<"毫秒。"<<endl;
    cout<<"unordered_map测试:开始。"<<endl;
    time1=clock();
    test_unordered_map();
    time2=clock();
    cout<<"unordered_map测试:"<<right<<setw(8)<<time2-time1<<"毫秒。"<<endl;
    cout<<"array_index测试:开始。"<<endl;
    time1=clock();
    test_array_index();
    time2=clock();
    cout<<"array_index测试:"<<right<<setw(8)<<time2-time1<<"毫秒。"<<endl;
    cout<<"array_reference测试:开始。"<<endl;
    time1=clock();
    test_array_reference();
    time2=clock();
    cout<<"array_reference测试:"<<right<<setw(8)<<time2-time1<<"毫秒。"<<endl;
    cout<<"array_pointer测试:开始。"<<endl;
    time1=clock();
    test_array_pointer();
    time2=clock();
    cout<<"array_pointer测试:"<<right<<setw(8)<<time2-time1<<"毫秒。"<<endl;
    system("pause");
    return 0;
}

void test_map()
{
    map<int,map<int,student_t>> schools;
    for(int i=0;i<MAP_STRESSING;i++)
    {
        map<int,student_t> students;
        for(int j=0;j<MAP_STRESSING;j++)
        {
            students[j].age=j;
            students[j].sex='F';
            students[j].a1=j;
            students[j].a2=j;
            students[j].a3=j;
            students[j].a4=j;
            students[j].a5=j;
            students[j].a6=j;
            students[j].a7=j;
            students[j].a8=j;
        }
        schools[i]=students;
    }
}

void test_unordered_map()
{
    unordered_map<int,unordered_map<int,student_t>> schools;
    for(int i=0;i<MAP_STRESSING;i++)
    {
        unordered_map<int,student_t> students;
        for(int j=0;j<MAP_STRESSING;j++)
        {
            students[j].age=21;
            students[j].sex='F';
            students[j].a1=j;
            students[j].a2=j;
            students[j].a3=j;
            students[j].a4=j;
            students[j].a5=j;
            students[j].a6=j;
            students[j].a7=j;
            students[j].a8=j;
        }
        schools[i]=students;
    }
}

void test_array_index()
{
    shared_ptr<school_t> schools(new school_t[ARRAY_STRESSING]);
    pschool_t pschools=schools.get();
    for(int i=0;i<ARRAY_STRESSING;i++)
    {
        pschools[i].id=i;
        for(int j=0;j<ARRAY_STRESSING;j++)
        {
            pschools[i].students[j].age=j;
            pschools[i].students[j].sex='F';
            pschools[i].students[j].a1=j;
            pschools[i].students[j].a2=j;
            pschools[i].students[j].a3=j;
            pschools[i].students[j].a4=j;
            pschools[i].students[j].a5=j;
            pschools[i].students[j].a6=j;
            pschools[i].students[j].a7=j;
            pschools[i].students[j].a8=j;
        }
    }
}

void test_array_reference()
{
    shared_ptr<school_t> schools(new school_t[ARRAY_STRESSING]);
    pschool_t pschools=schools.get();
    school_t& obj1=pschools[0];
    student_t& obj2=pschools[0].students[0];
    for(int i=0;i<ARRAY_STRESSING;i++)
    {
        obj1=pschools[i];
        obj1.id=i;
        for(int j=0;j<ARRAY_STRESSING;j++)
        {
            obj2=obj1.students[j];
            obj2.age=j;
            obj2.sex='F';
            obj2.a1=j;
            obj2.a2=j;
            obj2.a3=j;
            obj2.a4=j;
            obj2.a5=j;
            obj2.a6=j;
            obj2.a7=j;
            obj2.a8=j;
        }
    }
}

void test_array_pointer()
{
    shared_ptr<school_t> schools(new school_t[ARRAY_STRESSING]);
    pschool_t pschools=schools.get();
    pschool_t pobj1=nullptr;
    pstudent_t pobj2=nullptr;
    for(int i=0;i<ARRAY_STRESSING;i++)
    {
        pobj1=&pschools[i];
        pobj1->id=i;
        for(int j=0;j<ARRAY_STRESSING;j++)
        {
            pobj2=&pobj1->students[j];
            pobj2->age=j;
            pobj2->sex='F';
            pobj2->a1=j;
            pobj2->a2=j;
            pobj2->a3=j;
            pobj2->a4=j;
            pobj2->a5=j;
            pobj2->a6=j;
            pobj2->a7=j;
            pobj2->a8=j;
        }
    }
}

运行结果如下图所示:
图1
实验证明,同样的硬件环境与软件环境,同样的262144行数据的压力下,map类型用时13549毫秒,unordered_map类型用时5035毫秒,比map类型要快很多,但是和线性数组相比而言,它的速度不值一提:线程数组用时才5毫秒。
数组检索数据远不及map方便,如何把线性数组做的和map一样使用方便,我的下一篇博客将详细介绍。本文的源代码已经上传到码云上,GIT克隆地址:https://gitee.com/zhuangtaiqiusi/map_perfomance_demo.git

评论