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

Question

[dalbio]

Есть задача: 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 быстрее? (единственный мой вариант: из-за кеша, но я не уверен)
Спасибо за ответы

Answer 1

[Wataru]

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

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

Еще, чтобы избавиться от постоянных рехешированний можно добавить вот это:

len.reserve(1048576);
len.max_load_factor(0.25);

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

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

Comments

[dalbio]

Написал в начале программы, время работы 233 мс. Большое спасибо!)