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

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

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

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

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

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

Похожие вопросы
от 250 000 до 300 000 ₽
DevsVault Москва
от 200 000 до 350 000 ₽
SM Lab Железнодорожный
До 87 000 ₽
09 сент. 2024, в 18:27
400 руб./в час
09 сент. 2024, в 18:20
10000 руб./за проект
09 сент. 2024, в 17:53
7000 руб./за проект