Q&A
> ほぼ明らか
（頭弱い人の感想なのですが）
内部的にソートされた形でデータを保持する場所に対して，外部からソート済みのデータの塊が「ごっそりと」渡されるのだとしたら「ソートに必要な時間が減りそうかな？」と思えますが，
要素が１個ずつ渡される（且つ，それがソートされている順序で渡されてくるとは知らない）場合に関しては，ちょっと想像つかない感じ(?)です．
質問内容
Optimize C++(第3版)10.6.1節に「整列済みデータの挿入はそうでないデータの挿入より高速である(要約)」との記述があり、自分でも実験してみたところ確かに数倍程度高速に動作しているようでした。
ただ書籍ではその理由については触れられていませんでした。自分の考えとしては、整列済みデータの挿入の方が木に偏りが生じやすく、その結果として回転操作の回数が多くなりむしろ遅くなると思っていたのでこの結果は不思議です。どなたか詳しい方がいらっしゃれば、この結果となる理由についてお知恵を拝借できないでしょうか。
該当のソースコード
測定に使用したコードを記載します。
500000要素の重複のないベクトルを生成し、それを前から順番に1つずつmapへinsertします。
cpp
1#include <algorithm> 2#include <chrono> 3#include <functional> 4#include <iostream> 5#include <map> 6#include <random> 7#include <set> 8#include <vector> 9 10using namespace std; 11 12void build_rnd_vector(vector<int>& v, unsigned int count) 13{ 14 default_random_engine e; 15 uniform_int_distribution<unsigned int> d(count, count * 10 - 1); 16 auto randamizer = bind(d, e); 17 set<int> unique; 18 v.clear(); 19 while (v.size() < count) { 20 unsigned int rv = randamizer(); 21 if (unique.insert(rv).second) { 22 v.push_back(rv); 23 } 24 } 25} 26 27int main() 28{ 29 ios::sync_with_stdio(false); 30 cin.tie(nullptr); 31 32 chrono::system_clock::time_point start, end; 33 34 int count = 5000000; 35 36 map<int, int> mp; 37 vector<int> v; 38 build_rnd_vector(v, count); 39 40 // 整列させる 41 sort(v.begin(), v.end()); 42 43 start = chrono::system_clock::now(); 44 for (int i = 0; i < v.size(); ++i) { 45 mp.insert({ v[i], i }); 46 } 47 end = chrono::system_clock::now(); 48 double elapsed = chrono::duration_cast<chrono::milliseconds>(end - start).count(); 49 50 cout << "Elapsed Sec " << elapsed << " msec\n"; 51 52 return 0; 53}
非整列データの場合は途中のsort()をコメントアウトして計測しました。
AtCoderのコードテストでC++20(gcc 12.2)で計測してみたところ、Elapsed Secは以下のような結果となりました。
| 非整列 | 整列済み |
|---|---|
| 3884 | 1240 |
(msec)
回答4件
0
実装依存の話で"この実装で"と指定しないと議論になりませんが、ざっと検索すると赤黒木が一般的な実装みたいなのでその前提で考えました。
ソート済みのデータを順に挿入していくと、挿入位置の探索は根から見て常に右側に右側にと進みます。
また回転は確かに高い頻度で起こりますが、根から見て右側に探索する経路のどこかでしか起こらないはずです。（証明できないので断言はできませんが、回転は常に1回で済むはずです。ランダムだとたまに2回の回転が発生します）
それでメモリやCPUキャッシュやCPUの分岐予測が効きやすく、全体は速くなるのではないでしょうか?
Claude CodeにPythonで素朴な赤黒木の実装を作らせてみて様子を見たのですが、ソート済みのデータだとデータ数に対してとても線形に近い形で実行時間が伸びていきました。比較してランダムな順のデータだと掛かる時間の伸びが非線形になって、ある程度の個数以下だとランダムの方が速いが、どこかでソート済みの方が速くなる、という感じでした。
ソート済みのデータを渡すとほぼすべてで1回の回転が発生します。
ランダムにシャッフルしたデータを渡すと6割で回転なし、2割で1回の回転、2割で2回の回転、という雰囲気。
リカラーもソート済みのデータを渡した時の方が2倍くらい起きました。
ソード済みのデータを渡した時の方が起きる操作は明らかに多いです。
にも関わらず実行時間はソート済みのデータの方が短い（ある件数より多い場合）という傾向のようです。
"理論値として回転が少ないから速い"みたいなことではなくて、"実際に動かしたら速い"という話だから理由まで言及しなかったのだろうな、と感じました。
投稿2025/07/22 03:54
編集2025/07/22 09:52
総合スコア11357
0
手元の環境は Ubuntu Linux 24.10, g++ 14.2.0, libstdc++-v3 3.4.33 です。最初に、Linux で提供されている ltrace コマンド(library call tracer)でライブラリ関数が呼び出される回数を測定してみました。(手元の環境では計測に時間がかかるのでデータ数を 500,000 にしています)
ランダムデータ(重複なし)
$ g++ -std=gnu++17 -Wall -Wextra -g insert_random_generated_data_into_map.cc -o insert_random_generated_data_into_map $ ltrace -c -C ./insert_random_generated_data_into_map Elapsed Sec 98496 msec % time seconds usecs/call calls function ------ ----------- ----------- --------- -------------------- 28.50 53.956969 53 1000020 operator new(unsigned long) 28.43 53.828525 53 1000000 std::_Rb_tree_insert_and_rebalance(bool, std::_Rb_tree_node_base*, std::_Rb_tree_node_base*, std::_Rb_tree_node_base&) 28.40 53.765936 53 1000020 operator delete(void*, unsigned long) 14.67 27.771475 53 514938 std::_Rb_tree_decrement(std::_Rb_tree_node_base*) 0.00 0.002167 114 19 memcpy 0.00 0.000279 279 1 std::ios_base::sync_with_stdio(bool) 0.00 0.000185 61 3 std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*) 0.00 0.000178 89 2 std::chrono::_V2::system_clock::now() 0.00 0.000131 131 1 std::ostream::operator<<(std::ostream& (*)(std::ostream&)) 0.00 0.000085 85 1 std::ostream::operator<<(double) 0.00 0.000057 57 1 std::basic_ios<char, std::char_traits<char> >::tie(std::ostream*) ------ ----------- ----------- --------- -------------------- 100.00 189.325987 3515006 total
ソート済みデータ(上記のランダムデータをソート)
$ g++ -std=gnu++17 -Wall -Wextra -g insert_sorted_data_into_map.cc -o insert_sorted_data_into_map $ ltrace -c -C ./insert_sorted_data_into_map Elapsed Sec 78812 msec % time seconds usecs/call calls function ------ ----------- ----------- --------- -------------------- 30.66 54.264424 54 1000020 operator new(unsigned long) 30.62 54.195150 54 1000000 std::_Rb_tree_insert_and_rebalance(bool, std::_Rb_tree_node_base*, std::_Rb_tree_node_base*, std::_Rb_tree_node_base&) 30.59 54.134602 54 1000020 operator delete(void*, unsigned long) 8.13 14.394239 54 264953 std::_Rb_tree_decrement(std::_Rb_tree_node_base*) 0.00 0.002236 117 19 memcpy 0.00 0.000256 256 1 std::ios_base::sync_with_stdio(bool) 0.00 0.000248 82 3 std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*) 0.00 0.000175 87 2 std::chrono::_V2::system_clock::now() 0.00 0.000151 151 1 std::ostream::operator<<(std::ostream& (*)(std::ostream&)) 0.00 0.000090 90 1 std::basic_ios<char, std::char_traits<char> >::tie(std::ostream*) 0.00 0.000087 87 1 std::ostream::operator<<(double) ------ ----------- ----------- --------- -------------------- 100.00 176.991658 3265021 total
std::_Rb_tree_decrement(std::_Rb_tree_node_base*) の実行回数に顕著な違いが見られますが、_Rb_tree_decrement() は build_rnd_vector() 内の unique.insert(rv) と sort(v.begin(), v.end()) からも呼び出されため、単純に比較することはできません。
mp.insert({ v[i], i }); から _Rb_tree_decrement() までのバックトレースは以下の通りです。
mp.insert({ v[i], i });- insert()
- _M_insert_unique()
- _M_get_insert_unique_pos()
ここで、_M_get_insert_unique_pos() 内の --__j;の実体が operator--(int)となっていて(operator overloading)、operator--(int) 内で Rb_tree_decrement() が実行されることになります。
c++
1template<typename _Tp> 2struct _Rb_tree_iterator 3{ 4 : 5 _Self& 6 operator--() _GLIBCXX_NOEXCEPT 7 { 8 _M_node = _Rb_tree_decrement(_M_node); 9 return *this; 10 } 11 : 12 typedef _Rb_tree_iterator<value_type> iterator; 13 : 14} 15 : 16M_get_insert_unique_pos(const key_type& __k) 17{ 18 : 19 iterator __j = iterator(__y); 20 if (__comp) 21 { 22 if (__j == begin()) 23 return _Res(__x, __y); 24 else 25 --__j; // => _Rb_tree_iterator::operator--() 26 }
次に _M_get_insert_unique_pos() の実装について確認しておきたいと思います。なお、cpprefjp C++日本語リファレンスの map::insert には以下の様に記述されています。
map::insert - cpprefjp C++日本語リファレンス
内部的に map コンテナは、コンストラクト時に指定された比較オブジェクトによって要素を下位から上位へとソートして保持する。
以下のコードの最初の while ループ(while (__x != 0) { ... })は見ての通り二分探索(binary search)を行っていて、データの挿入位置を計算しています。ソート済みの一意データの場合、新たに登録されるキーデータはマップオブジェクトに登録されているキーデータよりも常に大きな値を持ちます。そのため __comp の値は初回登録時を除いて常に false になります。
c
1_M_get_insert_unique_pos(const key_type& __k) 2{ 3 typedef pair<_Base_ptr, _Base_ptr> _Res; 4 _Link_type __x = _M_begin(); 5 _Base_ptr __y = _M_end(); 6 bool __comp = true; 7 while (__x != 0) 8 { 9 __y = __x; 10 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 11 __x = __comp ? _S_left(__x) : _S_right(__x); 12 } 13 iterator __j = iterator(__y); 14 if (__comp) 15 { 16 if (__j == begin()) 17 return _Res(__x, __y); 18 else 19 --__j; 20 }
そこで map::insert() の実行過程での --__j; (_Rb_tree_decrement()) の実行回数を計測してみます。具体的には GDB を利用します。
count_comp.gdb
set pagination off # 最初に for (int i = 0; i < v.size(); ++i) {} の直前まで実行しておく break 44 commands 1 silent end run # 上記の for 文からカウントを開始 set $count = 0 break stl_tree.h:2123 ## --j; commands 2 silent end while(true) continue print $count++ end
実行
# ランダムデータ(重複なし) $ LD_LIBRARY_PATH=/usr/lib/x86_64-linux-gnu/debug/ gdb --batch --command=count_comp.gdb ./insert_random_generated_data_into_map $1 = 0 $2 = 1 : $249984 = 249983 $249985 = 249984 Elapsed Sec 91652 msec [Inferior 1 (process ...) exited normally] $249986 = 249985 # ソート済みデータ(上記のランダムデータをソート) $ LD_LIBRARY_PATH=/usr/lib/x86_64-linux-gnu/debug/ gdb --batch --command=count_comp.gdb ./insert_sorted_data_into_map Elapsed Sec 419 msec [Inferior 1 (process ...) exited normally] $1 = 0
ランダムデータの場合は249985回、ソート済みの場合は0回です。
投稿2025/07/27 09:22
総合スコア21527
0
へー、と思ったので、AIに聞いてみました。アルゴリズム系の話はAIが得意だと思ったので。以下、AIの回答です。
std::map へのソート済みデータの挿入が高速なのは、主に挿入位置の探索コストが大幅に削減されるためです。
ご指摘の通り、std::map は赤黒木という平衡二分探索木で実装されており、通常、要素の挿入にはキーの比較を繰り返して挿入位置を探すため、O(log n) の計算量がかかります。しかし、ソート済みのデータを順番に挿入する場合には、いくつかの最適化が働くことで、この探索が非常に効率的になります。
高速化の主な理由
1. 挿入ヒント（Hint）による最適化 📍
std::map::insert には、挿入位置のヒント（hint）をイテレータで与えることができるオーバーロードバージョンがあります。
cpp
1iterator insert(const_iterator hint, const value_type& value);
ソート済みのデータを順番に挿入する場合、次に追加する要素は常にコンテナの末尾（最も大きいキーを持つ要素の後）に来ることが分かっています。そのため、map.end() をヒントとして与えることで、std::map は木の根からではなく、ヒント周辺から探索を開始します。
もしヒントが正しければ（つまり、新しい要素がヒントの位置の直前に挿入される場合）、挿入位置の探索は 償却定数時間 O(1) で完了します。多くの標準ライブラリの実装では、ヒントの直後に挿入される場合でも同様に高速化されます。
cpp
1std::map<int, std::string> my_map; 2// ソート済みデータをループで挿入 3for (const auto& pair : sorted_data) { 4 // ヒントとして my_map.end() を渡すことで高速化が期待できる 5 my_map.insert(my_map.end(), pair); 6}
C++11以降では emplace_hint もあり、同様の最適化が得られます。
2. メモリの局所性とキャッシュ効率 🧠
ソート済みのデータを連続して挿入すると、新しいノードはメモリ上で物理的に近い位置に配置される可能性が高くなります。これにより、以下のメリットが生まれます。
- キャッシュヒット率の向上: CPUがメモリからデータを読み込む際、関連するデータがキャッシュに乗りやすくなります（空間的局所性）。
- メモリアクセスの高速化: ノード間のポインタをたどる際に、遠くのメモリアドレスにアクセスする必要が減り、メモリアクセスのレイテンシが削減されます。
一方、ランダムなデータを挿入すると、メモリのあちこちにノードが点在することになり、キャッシュミスが頻発してパフォーマンスが低下します。
懸念されていた点について
自分の考えとしては、整列済みデータの挿入の方が木に偏りが生じやすく、その結果として回転操作の回数が多くなりむしろ遅くなると思っていたのでこの結果は不思議です。
これは非常に良い着眼点です。確かに、ソート済みのデータを単純な二分探索木に挿入すると、木が線形リストのように偏ってしまい、性能が O(n) に悪化します。
しかし、std::map が使用する赤黒木は自己平衡機能を持っています。挿入によって木の平衡が崩れると、回転（rotation） と色の変更（re-coloring） を行って、木の高さが常に O(log n) に収まるように自動で調整します。
ソート済みデータの挿入では、確かにある程度の回転は発生しますが、そのコストは前述した探索コストの劇的な削減とキャッシュ効率の向上というメリットに比べれば十分に小さく、全体としてはランダムなデータを挿入するよりもはるかに高速になります。
まとめ
std::map へのソート済みデータの挿入が高速なのは、単に木が偏るからではなく、C++標準ライブラリに備わっている以下の仕組みによるものです。
- 挿入ヒントを利用することで、挿入位置の探索が O(log n) から O(1) に削減される。
- 連続したメモリアロケーションにより、CPUキャッシュの効率が向上する。
- 赤黒木の自己平衡機能が木の性能劣化を防いでくれる。
これらの要因が組み合わさることで、実験で観測されたような数倍の速度向上が実現されています。
投稿2025/07/24 01:26
総合スコア4960
0
こちらによれば、
内部的には、
map内の要素は、コンテナの構築時に設定された狭義の弱順序基準に従って小さいものから大きいものへとソートされる。
とあります。
内部的にソートがなされるものであれば、最初からソートしたものを入れたほうが余計なソートの手間が省ける、というのはほぼ明らかだと感じました。
投稿2025/07/22 02:13
総合スコア146853
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2025/07/22 19:05
2025/07/22 20:46 編集
2025/07/23 18:46