• C++ std map unordered_map hash_map 的查找性能测试代码及结果

    C++ std map unordered_map hash_map 的查找性能测试代码、过程及结果

    测试环境

    操作系统: Windows11专业版
    硬件环境：Intel i5-12500 3GHz 、16GB
    IDE：VS2019

    测试结果

    Release模式下：
    查找效率：unordered_map ≈ hash_map > map
    std::map 的效率远小于 unordered_map 和 hash_map

    Debug模式下：

    1. 查找效率：hash_map > unordered_map > map
    2. 随着容量的增加，hash_map, unordered_map的查找效率有所降低，但浮动不大毕竟是常量级别。map的效率直线下降。。。

    详细数据见本文下方的 测试过程记录

    测试代码

    #define _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS
#include 
#include 
#include 
#include 
#include 
namespace test_perf
{
class TimeCostCounter
{
public:
    explicit TimeCostCounter(const std::string& msg)
    {
        msg_ = new char[msg.size() + 1];
        strncpy_s(msg_, (msg.size() + 1), msg.c_str(), msg.size());
        start_ = std::chrono::system_clock::time_point(std::chrono::system_clock::now());

#if 0
        char output[512] = { 0 };
        _snprintf_s(output, sizeof(output) - 1,
            "enter time_const:%-7s microseconds  %s\r\n", "---", msg_);
        std::fprintf(stdout, "%s", output);
#endif // 0
    }
    ~TimeCostCounter()
    {
        std::chrono::system_clock::time_point time_end = std::chrono::system_clock::now();
        auto time_cust_t = std::chrono::duration_cast<std::chrono::microseconds>(time_end - start_);
        int cost_time = time_cust_t.count();

        char output[512] = { 0 };
        _snprintf_s(output, sizeof(output) - 1,
            "exit  time_const:%-7d microseconds  %s\r\n", cost_time, msg_);
        std::fprintf(stdout, "%s", output);

        delete msg_;
    }
    
private:
    std::chrono::system_clock::time_point start_;
    char* msg_ = nullptr;
};


// 测试函数，
// size     ：    map的实际大小
// times    ：    查找的轮次，每一轮次都从0查找到size-1
void test(int size, int times)
{
    std::cout << std::endl;
    std::cout << "begin test, size:" << size << "  times:" << times << std::endl;

    std::map<int, int>                m;
    std::unordered_map<int, int>      um;
    std::hash_map<int, int>           hm;

    // 初始化
    for (int i = 0; i < size; i++)
    {
        m[i] = i;
        um[i] = i;
        hm[i] = i;
    }

    int count_map = 0, count_unordered_map = 0, count_hash_map = 0;
    // map的查找
    {
        TimeCostCounter printer("test map");
        for (int i = 0; i < times; i++)
        {
            for (int j = 0; j < size; j++)
            {
                if (m.find(j) != m.end())
                {
                    count_map++;
                }
            }
        }
        //std::cout << "count:" << count_map << ", map:" << std::endl;
    }


    // unordered_map的查找
    {
        TimeCostCounter printer("test unordered_map");
        for (int i = 0; i < times; i++)
        {
            for (int j = 0; j < size; j++)
            {
                if (um.find(j) != um.end())
                {
                    count_unordered_map++;
                }
            }
        }
        //std::cout << "count:" << count_unordered_map << ", unordered_map:" << std::endl;
    }

    // hash_map的查找
    {
        TimeCostCounter printer("test hash_map");
        for (int i = 0; i < times; i++)
        {
            for (int j = 0; j < size; j++)
            {
                if (hm.find(j) != hm.end())
                {
                    count_hash_map++;
                }
            }
        }
        //std::cout << "count:" << count_hash_map << ", hash_map:" << std::endl;
    }
    std::cout << "count_map:" << count_map << "  count_unordered_map:" << count_unordered_map << "  count_hash_map:" << count_hash_map << std::endl;
}

int test_main()
{
    std::cout << "test begin..." << std::endl;

    test(10, 10000000);        // 容量：10         查找：1千万轮次
    test(100, 1000000);        // 容量：100        查找：1百万轮次
    test(1000, 100000);        // 容量：1000       查找：10万轮次
    test(10000, 10000);        // 容量：10000      查找：1万轮次
    test(100000, 1000);        // 容量：100000     查找：1000轮次
    test(1000000, 100);        // 容量：1000000    查找：100轮次
    test(10000000, 10);        // 容量：10000000   查找：10轮次

    std::cout << "test finished" << std::endl;

    return 0;
}
}  // namespace test_perf

int main()
{
    test_perf::test_main();

    int a = getchar();
    printf("a=%d", a);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142

    测试过程记录

    测试版本 RLEASE x64

    第一次测试

    test begin...

begin test, size:10  times:10000000
exit  time_const:377538  microseconds  test map
exit  time_const:185946  microseconds  test unordered_map
exit  time_const:231577  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:100  times:1000000
exit  time_const:680158  microseconds  test map
exit  time_const:174351  microseconds  test unordered_map
exit  time_const:219366  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:1000  times:100000
exit  time_const:2456112 microseconds  test map
exit  time_const:193982  microseconds  test unordered_map
exit  time_const:216137  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:10000  times:10000
exit  time_const:3935452 microseconds  test map
exit  time_const:262153  microseconds  test unordered_map
exit  time_const:246536  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:100000  times:1000
exit  time_const:3874978 microseconds  test map
exit  time_const:451669  microseconds  test unordered_map
exit  time_const:397784  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:1000000  times:100
exit  time_const:5637420 microseconds  test map
exit  time_const:2033308 microseconds  test unordered_map
exit  time_const:1697859 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:10000000  times:10
exit  time_const:5980635 microseconds  test map
exit  time_const:2049441 microseconds  test unordered_map
exit  time_const:2335847 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000
test finished

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    第二次测试

    test begin...

begin test, size:10  times:10000000
exit  time_const:387035  microseconds  test map
exit  time_const:194017  microseconds  test unordered_map
exit  time_const:219453  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:100  times:1000000
exit  time_const:658199  microseconds  test map
exit  time_const:178675  microseconds  test unordered_map
exit  time_const:219622  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:1000  times:100000
exit  time_const:2367859 microseconds  test map
exit  time_const:186760  microseconds  test unordered_map
exit  time_const:229742  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:10000  times:10000
exit  time_const:3969829 microseconds  test map
exit  time_const:258913  microseconds  test unordered_map
exit  time_const:254943  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:100000  times:1000
exit  time_const:3835890 microseconds  test map
exit  time_const:523620  microseconds  test unordered_map
exit  time_const:403951  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:1000000  times:100
exit  time_const:5635731 microseconds  test map
exit  time_const:2144435 microseconds  test unordered_map
exit  time_const:1756355 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:10000000  times:10
exit  time_const:6138499 microseconds  test map
exit  time_const:2386299 microseconds  test unordered_map
exit  time_const:2600038 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000
test finished

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    第三次测试

    test begin...

begin test, size:10  times:10000000
exit  time_const:383793  microseconds  test map
exit  time_const:179461  microseconds  test unordered_map
exit  time_const:246965  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:100  times:1000000
exit  time_const:696714  microseconds  test map
exit  time_const:184956  microseconds  test unordered_map
exit  time_const:240162  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:1000  times:100000
exit  time_const:2417398 microseconds  test map
exit  time_const:224808  microseconds  test unordered_map
exit  time_const:225643  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:10000  times:10000
exit  time_const:4034813 microseconds  test map
exit  time_const:265107  microseconds  test unordered_map
exit  time_const:235180  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:100000  times:1000
exit  time_const:3983721 microseconds  test map
exit  time_const:593352  microseconds  test unordered_map
exit  time_const:478527  microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:1000000  times:100
exit  time_const:5755605 microseconds  test map
exit  time_const:2157740 microseconds  test unordered_map
exit  time_const:1781829 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:10000000  times:10
exit  time_const:6350555 microseconds  test map
exit  time_const:2214270 microseconds  test unordered_map
exit  time_const:2407366 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000
test finished

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    测试版本 Debug x64

    第一次测试

    test begin...

begin test, size:10  times:10000000
exit  time_const:77725513 microseconds  test map
exit  time_const:55867924 microseconds  test unordered_map
exit  time_const:50301682 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:100  times:1000000
exit  time_const:103791587 microseconds  test map
exit  time_const:57031541 microseconds  test unordered_map
exit  time_const:53823537 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:1000  times:100000
exit  time_const:116249684 microseconds  test map
exit  time_const:55005075 microseconds  test unordered_map
exit  time_const:52733354 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:10000  times:10000
exit  time_const:141760952 microseconds  test map
exit  time_const:60648988 microseconds  test unordered_map
exit  time_const:54216907 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:100000  times:1000
exit  time_const:164759336 microseconds  test map
exit  time_const:75498544 microseconds  test unordered_map
exit  time_const:66905100 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:1000000  times:100
exit  time_const:195118169 microseconds  test map
exit  time_const:76603801 microseconds  test unordered_map
exit  time_const:70866936 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000

begin test, size:10000000  times:10
exit  time_const:223320650 microseconds  test map
exit  time_const:77281447 microseconds  test unordered_map
exit  time_const:73711380 microseconds  test hash_map
count_map:100000000  count_unordered_map:100000000  count_hash_map:100000000
test finished

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
  • 相关阅读:
    VuePress + GitHub 搭建个人博客踩坑记录
    MR混合现实实训系统为农学情景实训教学演练
    npm的基础
    Labview 前面板放置照片
    iOS代码混淆-从入门到放弃
    Webrtc支持FFMPEG硬解码之解码实现（三）
    Java获取AD域内所有用户
    剑指 Offer II 039. 直方图最大矩形面积
    list排序根据某个字段去重
    .Net CLR GC动态获取函数头地址，C++的骚操作（慎入）
  • 原文地址：https://blog.csdn.net/shadow_2011/article/details/128040178