はじめに
趣味で AtCoder のコンテストに参加するようになって、中途半端な勉強した結果、逆に実装が雑になってしまっている部分もあります。
特に最近、「 昇順ソートされている数列 が作りたいなぁ。とりあえず std::set に突っ込んでおこう」程度の発想でコンテナを選んだら、TLEが出てしまって原因の切り分けに苦しむことが複数回ありました。
コンテナ内部のデータ構造を考えれば差はあるだろうけど、言ぅてそんな極端な差はないのでは？ という気持ちでいたので、ここらで std::set は重い という話を体感してみようと、テストプログラムを書いて処理時間を計測してみた記録です。
環境
我が家の PC の WSL2
バックグラウンドでもいろいろ動いているので、それほど厳密には測定してません。
測定結果①： 構築
ランダムで生成した 64bit整数 $2 \times 10^5$ 個をテキストファイルから読み込んで、昇順ソートされている状態にするまでの処理時間(単位:マイクロ秒)
vector は push_back() でメモリを拡張しています。
| case | priority_queue | vector + sort | set |
|---|---|---|---|
| 1 | 118540 | 143572 | 215521 |
| 2 | 121401 | 145315 | 218956 |
| 3 | 123471 | 150026 | 215841 |
| 4 | 119003 | 151527 | 211504 |
| 5 | 118323 | 146019 | 208502 |
測定結果②： 複製(コピーコンストラクタ)
| case | priority_queue | vector | set |
|---|---|---|---|
| 1 | 446 | 403 | 34641 |
| 2 | 662 | 413 | 33037 |
| 3 | 625 | 498 | 33978 |
| 4 | 456 | 452 | 32136 |
| 5 | 456 | 393 | 33350 |
結論
重いわ。
せっかくだから std::set が得意なはずのノード削除とか、二分探索の処理時間も測ろうと思ってましたが、打ち切りました。
今後はソートされていてほしい程度の意図で std::set は使わないことにします