@dalbio

# Почему в данной ситуации map быстрее unordered_map?

Есть задача: https://codeforces.com/contest/1283/problem/D
и 2 решения
1-e с unordered_map ( >2000 мс):
``````#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define double long double
#define sqr(x) (x)*(x)
#define pb push_back
#define ams(a) for (auto&c:a) cout<<c<<" ";
#define pf push_front
int32_t main() {
IOS;
int n, m;
cin >> n >> m;
queue<int>q;
unordered_map<int, int>len;
for (int i = 0; i < n; i++) {
int x; cin >> x; len[x] = 0;
q.push(x + 1); q.push(x - 1);
}
vector<int>ans;
int sum = 0;
while (1) {
if (ans.size() == m) break;
int cur = q.front(); q.pop();
if (!len.count(cur)) {
int r1 = 1e18; int r2 = 1e18;
if (len.count(cur - 1)) r1 = len[cur - 1];
if (len.count(cur + 1)) r2 = len[cur + 1];
if (min(r1, r2) == 1e18) continue;
sum += min(r1, r2) + 1; len[cur] = min(r1, r2) + 1;
q.push(cur - 1); q.push(cur + 1); ans.pb(cur);
}
}
cout << sum << "\n";
ams(ans);
}``````

2-е с map (607 мс):
``````#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define double long double
#define sqr(x) (x)*(x)
#define pb push_back
#define ams(a) for (auto&c:a) cout<<c<<" ";
#define pf push_front
int32_t main() {
IOS;
int n, m;
cin >> n >> m;
queue<int>q;
map<int, int>len;
for (int i = 0; i < n; i++) {
int x; cin >> x; len[x] = 0;
q.push(x + 1); q.push(x - 1);
}
vector<int>ans;
int sum = 0;
while (1) {
if (ans.size() == m) break;
int cur = q.front(); q.pop();
if (!len.count(cur)) {
int r1 = 1e18; int r2 = 1e18;
if (len.count(cur - 1)) r1 = len[cur - 1];
if (len.count(cur + 1)) r2 = len[cur + 1];
if (min(r1, r2) == 1e18) continue;
sum += min(r1, r2) + 1; len[cur] = min(r1, r2) + 1;
q.push(cur - 1); q.push(cur + 1); ans.pb(cur);
}
}
cout << sum << "\n";
ams(ans);
}``````

Почему в данной ситуации map быстрее? (единственный мой вариант: из-за кеша, но я не уверен)
Спасибо за ответы
• Вопрос задан
• 45 просмотров
Решения вопроса 1
@wataru
Разработчик на С++, гуглер, экс-олимпиадник.
unordered_map может работать за линию в худшем случае. Это если происходит много коллизий. Стандартная реализация еще и дико медленная, через связные списки работает и часто использует тривиальные хеши (буквально, значение int берется за значение хеша). Подобрать смертельный тест для такого хэша совсем не сложно. Введите вашей программе на вход координаты деревьев i*8192 - если я правильно понимаю, unordered_map будет работать ооочень долго.

Можно избавиться от таких тривиальных коллизий, если реализовать свою хеш функцию. А там можно хоть `(x * 239017l) % (1<<31)` возвращать. И то, лучше будет.

Еще, чтобы избавиться от постоянных рехешированний можно добавить вот это:
``````len.reserve(1048576);

Говорят, что если заранее зарезервировать место и указать load_factor поменьше, то unordered_map будет раз в 10 быстрее.

Плюс, константа у unorderd_map выше - ибо надо хеши считать и перехешировать всю таблицу, если чисел становится много. Может, оно бы было быстрее для миллиона чисел, а не 100000, как у вас там.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

### Войдите, чтобы написать ответ

Похожие вопросы
AMICUM Кемерово
от 45 000 до 120 000 ₽
CarPrice Москва
от 80 000 ₽
Сима-ленд Екатеринбург
от 100 000 ₽
24 янв. 2021, в 22:45
2000 руб./за проект
23 янв. 2021, в 19:50
3000 руб./за проект
24 янв. 2021, в 21:49
5000 руб./за проект