👻

[c++] グラフの辺に、隣接リスト、隣接行列。unordered_set.find()に意外と時間がかかった。

2022/10/15に公開

C++

プログラミング

tech

(使用した問題)
032 - AtCoder Ekiden（★3）

この問題を解くときに、グラフの辺を表すのに、unordered_setを使って隣接リストを作成しました。
この問題では、辺が存在するかチェックするので、vectorよりunordered_setのほうがいいかなと思い、unordered_setを使っています(unordered_set.find()で存在チェックする)

vector<unordered_set<int>> edge(N);

実行時間、　メモリ
283 ms、　3648 KB

すると、他の人の解答より3～4倍ほど時間がかかってました。
そこで、隣接行列に変更してみました

    vector<vector<int>> edge(N, vector<int>(N, 0));

実行時間、　メモリ
54 ms、　3668 KB

一番時間がかかっているテストケースでは、辺の数が0個になってました。
なので、単純に値の検索にかかる時間で、
トータルの実行時間に差が出てきているということになると思います。

~~今回の場合、vectorの値取得(vector[i])と、unordered_setの値検索(unordered_set.find(i))による違いになります。~~

個人的にset型の値検索は、速いイメージだったので、意外でした。
(配列の値取得と比べたら、遅いのは当たり前なのかもしれませんが)

よく考えたら、unordered_setの初期化に時間がかかった可能性が高いですかね

code(隣接リスト)

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
#include <math.h>
#include <numeric>
#include <algorithm>


int main() {
    int N;
    cin >> N;

    vector<vector<int>> A(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    int M;
    cin >> M;

    vector<int> X(M), Y(M);
    for (int i = 0; i < M; i++) {
        cin >> X[i] >> Y[i];
        X[i]--;
        Y[i]--;
    }

    vector<unordered_set<int>> edge(N);
    for (int i = 0; i < M; i++) {
        edge[X[i]].insert(Y[i]);
        edge[Y[i]].insert(X[i]);
    }

    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    int INF = 10000 + 10;
    int ans = INF;

    do {
        int total = 0;
        bool flag = true;
        for (int i = 0; i < (N-1); i++) {
            if (edge[order[i]].find(order[i+1]) != edge[order[i]].end()) {
                flag = false;
                break;
            }
            total += A[order[i]][i];
        }
        if (flag) {
            total += A[order[N-1]][N-1];
            ans = min(ans, total);
        }
    } while (next_permutation(order.begin(), order.end()));

    if (ans == INF) {
        printf("-1\n");
    } else {
        printf("%d\n", ans);
    }
}

code(隣接行列)

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
#include <math.h>
#include <numeric>
#include <algorithm>


int main() {
    int N;
    cin >> N;

    vector<vector<int>> A(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    int M;
    cin >> M;

    vector<int> X(M), Y(M);
    for (int i = 0; i < M; i++) {
        cin >> X[i] >> Y[i];
        X[i]--;
        Y[i]--;
    }

    vector<vector<int>> edge(N, vector<int>(N, 0));
    for (int i = 0; i < M; i++) {
        edge[X[i]][Y[i]] = 1;
        edge[Y[i]][X[i]] = 1;
    }

    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    int INF = 10000 + 10;
    int ans = INF;

    do {
        int total = 0;
        bool flag = true;

        for (int i = 0; i < (N-1); i++) {
            if (edge[order[i]][order[i+1]] == 1) {
                flag = false;
                break;
            }
            total += A[order[i]][i];
        }
        if (flag) {
            total += A[order[N-1]][N-1];
            ans = min(ans, total);
        }
    } while (next_permutation(order.begin(), order.end()));

    if (ans == INF) {
        printf("-1\n");
    } else {
        printf("%d\n", ans);
    }
}

code(隣接リスト)

code(隣接行列)

Discussion