首页 > 编程语言 > 详细

关于c++ STL map 和 unordered_map 的效率的对比测试

时间:2021-08-12 23:31:46      阅读:35      评论:0      收藏:0      [点我收藏+]

单 int测试

插入范围 查询范围 map插入时间 map查询时间 unordered_map插入时间 unordered_map查询时间
10000 10000 11.95ms 10.268ms 15.184ms 5.009ms
100000 100000 113.374ms 134.365ms 200.852ms 79.029ms
1000000 1000000 1606.66ms 1819.2ms 2603.46ms 862.877ms
10000000 10000000 21688.5ms 25461.7ms 33973.7ms 9484.45ms
#include <bits/stdc++.h>

using namespace std;

int main()
{
    for(int n = 1e4, m = 1e4; n <= 1e9, m <= 1e9; n *= 10,m *= 10)
    {
        cout << n << "|" << m ;
        srand(n);
        int t0 = clock();
        map <int ,int> M;
        for(int i = 1; i <= n; i++)
        {
            M[rand()] = i;
        }
        cout << "| " << (double)(clock() - t0) / 1000 << "ms ";
        unsigned sum = 0;
        t0 = clock();
        for(int i = 1; i <= m; i++)
        {
            sum += M[rand()];
        }
        cout << "| " << (double)(clock() - t0) / 1000 << "ms ";
        srand(n);
        unordered_map <int, int> U;
        for(int i = 1; i <= n; i++)
        {
            U[rand()] = i;
        }
        cout << "| " << (double)(clock() - t0) / 1000 << "ms ";
        sum = 0;
        t0 = clock();
        for(int i = 1; i <= m; i++)
        {
            sum += U[rand()];
        }
        cout << "| " << (double)(clock() - t0) / 1000 << "ms |" << endl;
    }
    return 0;
}

二元组测试

插入范围 查询范围 map插入时间 map查询时间 unordered_map插入时间 unordered_map查询时间
10000 10000 10.617ms 11.523ms 16.301ms 5.14ms
100000 100000 122.489ms 141.413ms 195.278ms 70.122ms
1000000 1000000 1792.69ms 2173.48ms 2879.21ms 783.437ms
10000000 10000000 25017.8ms 28777.1ms 36499.8ms 8666.73ms
#include <bits/stdc++.h>

using namespace std;
struct PII
{
    int x, y;

    bool operator ==(const PII b) const
    {
        return x == b.x && y == b.y;
    }

    bool operator <(const PII b) const
    {
        return x != b.x ? x < b.x : y < b.y;
    }

};

struct hashPII
{
    size_t operator()(const PII &p) const
    {
        return hash<int>()(p.x) ^ hash<int>()(p.y);
    }
};

int main()
{
    for(int n = 1e4, m = 1e4; n <= 1e9, m <= 1e9; n *= 10,m *= 10)
    {
        cout << n << "|" << m ;
        srand(n);
        int t0 = clock();
        map <PII ,int> M;
        for(int i = 1; i <= n; i++)
        {
            M[{rand(), rand()}] = i;
        }
        cout << "| " << (double)(clock() - t0) / 1000 << "ms ";
        unsigned sum = 0;
        t0 = clock();
        for(int i = 1; i <= m; i++)
        {
            sum += M[{rand(), rand()}];
        }
        cout << "| " << (double)(clock() - t0) / 1000 << "ms ";
        srand(n);
        unordered_map <PII, int, hashPII> U;
        for(int i = 1; i <= n; i++)
        {
            U[{rand(), rand()}] = i;
        }
        cout << "| " << (double)(clock() - t0) / 1000 << "ms ";
        sum = 0;
        t0 = clock();
        for(int i = 1; i <= m; i++)
        {
            sum += U[{rand(), rand()}];
        }
        cout << "| " << (double)(clock() - t0) / 1000 << "ms |" << endl;
    }
    return 0;
}

三元组测试


插入范围 查询范围 map插入时间 map查询时间 unordered_map插入时间 unordered_map查询时间
10000 10000 9.265ms 10.061ms 14.415ms 4.325ms
100000 100000 127.82ms 141.59ms 196.931ms 70.29ms
1000000 1000000 1700.73ms 1971.21ms 2685.96ms 782.957ms

O2

单 int测试

插入范围 查询范围 map插入时间 map查询时间 unordered_map插入时间 unordered_map查询时间
10000 10000 2.103ms 2.617ms 3.775ms 1.261ms
100000 100000 46.243ms 67.461ms 86.591ms 34.024ms
1000000 1000000 822.828ms 1056.85ms 1412.39ms 422.122ms
10000000 10000000 13690.2ms 16854.1ms 20994.4ms 4903.84ms

二元组测试

插入范围 查询范围 map插入时间 map查询时间 unordered_map插入时间 unordered_map查询时间
10000 10000 2.463ms 3.461ms 4.908ms 2.209ms
100000 100000 61.531ms 89.114ms 127.359ms 49.821ms
1000000 1000000 1301.74ms 1692.79ms 2184.67ms 585.508ms
10000000 10000000 21245.7ms 24632.5ms 30906.3ms 7312.4ms

关于c++ STL map 和 unordered_map 的效率的对比测试

原文:https://www.cnblogs.com/lyc-lb-blogs/p/15134298.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!