回答編集履歴
2
追記
answer
CHANGED
|
@@ -7,4 +7,11 @@
|
|
|
7
7
|
|
|
8
8
|
----
|
|
9
9
|
|
|
10
|
-
Claude CodeにPythonで素朴な赤黒木の実装を作らせてみて様子を見たのですが、ソート済みのデータだとデータ数に対してとても線形に近い形で実行時間が伸びていきました。比較してランダムな順のデータだと掛かる時間の伸びが非線形になって、ある程度の個数以下だとランダムの方が速いが、どこかでソート済みの方が速くなる、という感じでした。
|
|
10
|
+
Claude CodeにPythonで素朴な赤黒木の実装を作らせてみて様子を見たのですが、ソート済みのデータだとデータ数に対してとても線形に近い形で実行時間が伸びていきました。比較してランダムな順のデータだと掛かる時間の伸びが非線形になって、ある程度の個数以下だとランダムの方が速いが、どこかでソート済みの方が速くなる、という感じでした。
|
|
11
|
+
|
|
12
|
+
ソート済みのデータを渡すとほぼすべてで1回の回転が発生します。
|
|
13
|
+
ランダムにシャッフルしたデータを渡すと6割で回転なし、2割で1回の回転、2割で2回の回転、という雰囲気。
|
|
14
|
+
リカラーもソート済みのデータを渡した時の方が2倍くらい起きました。
|
|
15
|
+
ソード済みのデータを渡した時の方が**起きる操作は明らかに多い**です。
|
|
16
|
+
**にも関わらず実行時間はソート済みのデータの方が短い**（ある件数より多い場合）という傾向のようです。
|
|
17
|
+
"理論値として回転が少ないから速い"みたいなことではなくて、"実際に動かしたら速い"という話だから理由まで言及しなかったのだろうな、と感じました。
|
1
些細
answer
CHANGED
|
@@ -1,7 +1,7 @@
|
|
|
1
1
|
実装依存の話で"この実装で"と指定しないと議論になりませんが、ざっと検索すると赤黒木が一般的な実装みたいなのでその前提で考えました。
|
|
2
2
|
|
|
3
3
|
ソート済みのデータを順に挿入していくと、挿入位置の探索は根から見て常に右側に右側にと進みます。
|
|
4
|
-
また回転は確かに高い頻度で起こりますが、根から見て右側に探索する経路のどこかでしか起こらないはずです。（証明できないので断言はできませんが、回転は常に1回で済むはずです。ランダムだと2回の回転が発生します）
|
|
4
|
+
また回転は確かに高い頻度で起こりますが、根から見て右側に探索する経路のどこかでしか起こらないはずです。（証明できないので断言はできませんが、回転は常に1回で済むはずです。ランダムだとたまに2回の回転が発生します）
|
|
5
5
|
|
|
6
6
|
それでメモリやCPUキャッシュやCPUの分岐予測が効きやすく、全体は速くなるのではないでしょうか?
|
|
7
7
|
|