本文采用在随机读取和插入的情况下测试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) ?\)读取具有很大的性能优势