【22日目】コンテナ毎の速度の違いについて

昨日の分です。最近遅れ気味なのは反省してます。。

---

先日

23　JOI 2008 本選 3 - ダーツ

でなぜかTLEになった問題。結局コンテナとしてsetを使っていたのをvectorに直したら制限時間内に計算できたのだが、そこで

コンテナ毎に実行時間にはどの程度差があるのか？

ということを疑問に思い、調べてみた。

具体的には、 * 各コンテナ(vector, set, multiset)に10⁶個の値を昇順に格納する * vectorの場合は格納してからソートする ということをやってその実行時間をclock関数で計測。コンパイラはGCC。

コードは以下の通り。

    start = clock();
    vector<int> a(N);
    for(int i=0; i<N; ++i) a[i] = s[i];
    sort(a.begin(), a.end());
    end = clock();
    cout << (double)(end - start)/CLOCKS_PER_SEC << " sec." << endl;

    start = clock();
    multiset<int> c;
    for(int i=0; i<N; ++i) c.insert(s[i]);
    end = clock();
    cout << (double)(end - start)/CLOCKS_PER_SEC << " sec." << endl;

setは省略。

結果…

• vector -> 0.312 s
• multiset -> 1.958 s
• set -> 0.065 s

というわけでとりあえずmultisetはめちゃくちゃ遅いということは分かった。これはどのコンパイラでも大差なかったからこういうものなのだと思う。今度から使うのやめよ。。

一方、今回ネックとなっていたはずのsetはむしろかなり高速という結果に。他の操作(イテレータ走査、二分探索など)も試したが全く遅いということはなかった。じゃああのTLEの原因は何だったんだ？？真相は謎のままである。