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

时间：2024-02-15 11:29:03

本文采用在随机读取和插入的情况下测试map和unordered_map的效率

笔者的电脑是台渣机，现给出配置信息

处理器 ： Intel® Pentium(R) CPU G850 @ 2.90GHz × 2
内存 ： 7.7GiB
操作系统 ： Ubuntu 20.04.2 LTS 64位(Noi Linux 2.0)

由于在数据量小的情况下二者时间差异微乎其微，测试范围从1e4开始到1e7，map unordered_map存储为 int, int二元组，int三元组

单 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

理论复杂度

map<int, int> unordered_map<int, int>
插入 \(O(log( n ) )\) \(O(log(n / m)\) m = 桶数
读取 \(O(log( n ) )\) \(O(1) ？\)

可以发现随着数据量的增大unordered_map在插入上由于冲突，性能是不及map的插入\(O(logn)\)的，但是其优秀的\(O(1) ?\)读取具有很大的性能优势

相关文章