ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

std::set の for アクセスは遅い(C++)

C++

知らなかった～。

コンパイル環境

コンパイラバージョン

> gcc --version
gcc.exe (Rev6, Built by MSYS2 project) 10.2.0
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

コンパイラオプション

g++.exe -g a.cpp -o a.exe -std=c++17 -Wall -Wextra

std::set の時間計測

#include <iostream>
#include <vector>
#include <set>
#include <chrono>

void solve() {
    std::set<int> T;
    for(int i=0; i<200000; i++) {
        T.insert(i);
    }

    auto start = std::chrono::system_clock::now(); // 計測開始時間

    // for アクセスの時間を計測する
    int tmp = 0;
    for(int n=0; n<=1000; n++) {
        for(int val: T) {
            tmp += val;
        }
    }

    auto end = std::chrono::system_clock::now();  // 計測終了時間
    double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count(); //処理に要した時間をミリ秒に変換
    printf("%.3f\n", elapsed);
}


int main() {
    solve();
    return 0;
}

出力結果

5057.000

std::vector の時間計測

#include <iostream>
#include <vector>
#include <set>
#include <chrono>

void solve() {
    std::vector<int> V;
    for(int i=0; i<200000; i++) {
        V.push_back(i);
    }

    auto start = std::chrono::system_clock::now(); // 計測開始時間

    // for アクセスの時間を計測する
    int tmp = 0;
    for(int n=0; n<=1000; n++) {
        for(int val: V) {
            tmp += val;
        }
    }

    auto end = std::chrono::system_clock::now();  // 計測終了時間
    double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count(); //処理に要した時間をミリ秒に変換
    printf("%.3f\n", elapsed);
}


int main() {
    solve();
    return 0;
}

出力結果

1375.000

雑な計測ですが、4倍程度違います。

setを使ってTLEする例

ABC 144 F - Fork in the Roadでsetを使うとTLEして、vectorを使うとACしました。

以下の2つのコードの違いは21,22行目と、25,26行目だけです。

最初、TLEの原因は25行目のinsert()の対数時間が増えたことだと思ったのですが、それにしてもTLEするほどの速度差が出るのはおかしいと思って調べたところ、そうではなくて、52, 64, 73行目のforループが遅いことが原因でした。

forループが遅いってどういうこと？と思いましたが、冷静に考えればsetは平衡二分探索木なので、平衡二分探索木のノードを辿る動作に思いを馳せればたしかにとなりました。というかunordered_setを使えば良かったのかも、と思って提出してみたらギリギリACしました。

「G[u] := 頂点uに隣接する頂点リスト（集合）」というのを構築するとき、よく「頂点vは頂点uに隣接するか？」という検索をしたい気持ちになるのでsetを好んで使っていましたが、その弊害が出てしまいました。