Здравствуйте!
Имеется следующий агрегат:
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
int n,m;
int d;
vector<char> used;
long long cnt = 0;
void dfs(int v){
if (used[v]) return;
used[v] = true;
cnt++;
for (int to: G[v])
dfs(to);
}
int main() {
ios_base::sync_with_stdio(0);
cin >> n >> m >> d;
G.resize(n);
for (int i = 0; i<m; ++i){
int x, y; cin >> x >> y;
G[x].push_back(y);
}
for (int i = 0; i<n; ++i)
sort(G[i].begin(), G[i].end());
int start = clock();
used.resize(n,0);
for (int i = 0; i<d; ++i){
fill(used.begin(), used.end(), 0);
for (int v = 0; v<n; ++v)
dfs(v);
}
printf("cnt = %lld\n%.4fsec\n",cnt, (float)(clock() - start)/CLOCKS_PER_SEC);
return 0;
}
Запускаю его на большом графе(n,m > 10^5) при d = 1000, подавая на вход дуги вперемешку, получаю 8sec. Запускаю на том же графе, подавая дуги в отсортированном порядке, получаю 1.2 сек.
Когда на вход дуги подаются в таком порядке, что сначала полностью заполняется G[0]
, затем G[1]
, G[2]
, ..., G[n-1]
, все отрабатывает намного быстрее, чем, если дуги подаются вперемешку.
Есть предположение, что это из-за неудачного размещения их в памяти и частых кеш-промахов. Отсюда вопрос: как в таком случае будут размещены элементы векторов?
Хотя, возможно, это связано с чем-то другим, тогда вопрос: из-за чего еще такое может происходить?