c# - ツリーへの挿入は、ランダム入力よりもソートされた入力の方が速いのはなぜですか?

Question

二分探索木は、順序付けられたデータよりもランダムに選択されたデータから構築する方が速いといつも聞いています。これは、順序付けられたデータでは、ツリーの高さを最小限に保つために明示的な再調整が必要だからです。

最近、私は不変のtrapを実装しました。これは、ランダム化を使用して比較的バランスを保つ特別な種類の二分探索ツリーです。私が予想していたものとは対照的に、順序付けられていないデータよりも順序付けられたデータの方が約 2 倍速く、一般的によりバランスの取れた Treap を一貫して構築できることがわかりました。その理由はわかりません。

これが私の Treap の実装です。

• http://pastebin.com/VAfSJRwZ

そして、ここにテストプログラムがあります：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

namespace ConsoleApplication1
{

    class Program
    {
        static Random rnd = new Random();
        const int ITERATION_COUNT = 20;

        static void Main(string[] args)
        {
            List<double> rndTimes = new List<double>();
            List<double> orderedTimes = new List<double>();

            rndTimes.Add(TimeIt(50, RandomInsert));
            rndTimes.Add(TimeIt(100, RandomInsert));
            rndTimes.Add(TimeIt(200, RandomInsert));
            rndTimes.Add(TimeIt(400, RandomInsert));
            rndTimes.Add(TimeIt(800, RandomInsert));
            rndTimes.Add(TimeIt(1000, RandomInsert));
            rndTimes.Add(TimeIt(2000, RandomInsert));
            rndTimes.Add(TimeIt(4000, RandomInsert));
            rndTimes.Add(TimeIt(8000, RandomInsert));
            rndTimes.Add(TimeIt(16000, RandomInsert));
            rndTimes.Add(TimeIt(32000, RandomInsert));
            rndTimes.Add(TimeIt(64000, RandomInsert));
            rndTimes.Add(TimeIt(128000, RandomInsert));
            string rndTimesAsString = string.Join("\n", rndTimes.Select(x => x.ToString()).ToArray());

            orderedTimes.Add(TimeIt(50, OrderedInsert));
            orderedTimes.Add(TimeIt(100, OrderedInsert));
            orderedTimes.Add(TimeIt(200, OrderedInsert));
            orderedTimes.Add(TimeIt(400, OrderedInsert));
            orderedTimes.Add(TimeIt(800, OrderedInsert));
            orderedTimes.Add(TimeIt(1000, OrderedInsert));
            orderedTimes.Add(TimeIt(2000, OrderedInsert));
            orderedTimes.Add(TimeIt(4000, OrderedInsert));
            orderedTimes.Add(TimeIt(8000, OrderedInsert));
            orderedTimes.Add(TimeIt(16000, OrderedInsert));
            orderedTimes.Add(TimeIt(32000, OrderedInsert));
            orderedTimes.Add(TimeIt(64000, OrderedInsert));
            orderedTimes.Add(TimeIt(128000, OrderedInsert));
            string orderedTimesAsString = string.Join("\n", orderedTimes.Select(x => x.ToString()).ToArray());

            Console.WriteLine("Done");
        }

        static double TimeIt(int insertCount, Action<int> f)
        {
            Console.WriteLine("TimeIt({0}, {1})", insertCount, f.Method.Name);

            List<double> times = new List<double>();
            for (int i = 0; i < ITERATION_COUNT; i++)
            {
                Stopwatch sw = Stopwatch.StartNew();
                f(insertCount);
                sw.Stop();
                times.Add(sw.Elapsed.TotalMilliseconds);
            }

            return times.Average();
        }

        static void RandomInsert(int insertCount)
        {
            Treap<double> tree = new Treap<double>((x, y) => x.CompareTo(y));
            for (int i = 0; i < insertCount; i++)
            {
                tree = tree.Insert(rnd.NextDouble());
            }
        }

        static void OrderedInsert(int insertCount)
        {
            Treap<double> tree = new Treap<double>((x, y) => x.CompareTo(y));
            for(int i = 0; i < insertCount; i++)
            {
                tree = tree.Insert(i + rnd.NextDouble());
            }
        }
    }
}

そして、ランダム挿入時間と順序付き挿入時間をミリ秒単位で比較したグラフを次に示します。

Insertions         Random          Ordered         RandomTime / OrderedTime
50                 1.031665        0.261585        3.94
100                0.544345        1.377155        0.4
200                1.268320        0.734570        1.73
400                2.765555        1.639150        1.69
800                6.089700        3.558350        1.71
1000               7.855150        4.704190        1.67
2000               17.852000       12.554065       1.42
4000               40.157340       22.474445       1.79
8000               88.375430       48.364265       1.83
16000              197.524000      109.082200      1.81
32000              459.277050      238.154405      1.93
64000              1055.508875     512.020310      2.06
128000             2481.694230     1107.980425     2.24

順序付けられた入力を順序付けられていない入力よりも漸近的に高速にするコードは何も見られないため、違いを説明するのに途方に暮れています。

ランダム入力よりも順序付けられた入力からトレプを構築する方がはるかに速いのはなぜですか?

Answer 1

コードを実行しましたが、回転数に関係していると思います。順序付けられた入力中、回転数は最適であり、ツリーが逆回転する必要はありません。

ランダムな入力中、ツリーは前後に回転する必要があるため、より多くの回転を実行する必要があります。

実際に調べるには、実行ごとに左右の回転数のカウンターを追加する必要があります。あなたはおそらくこれを自分で行うことができます。

アップデート：

ローテートレフトとローテートライトにブレークポイントを設定しました。順序付けられた入力中は、rotateright は使用されません。ランダム入力時はどちらも当たりで、こちらの方が使用頻度が高い気がします。

更新 2:

詳細を確認するために、50 アイテムの注文実行にいくつかの出力を追加しました (わかりやすくするために整数に置き換えています)。

TimeIt(50, OrderedInsert)
LastValue = 0, Top.Value = 0, Right.Count = 0, Left.Count = 0
RotateLeft @value=0
LastValue = 1, Top.Value = 1, Right.Count = 0, Left.Count = 1
LastValue = 2, Top.Value = 1, Right.Count = 1, Left.Count = 1
LastValue = 3, Top.Value = 1, Right.Count = 2, Left.Count = 1
RotateLeft @value=3
RotateLeft @value=2
RotateLeft @value=1
LastValue = 4, Top.Value = 4, Right.Count = 0, Left.Count = 4
LastValue = 5, Top.Value = 4, Right.Count = 1, Left.Count = 4
LastValue = 6, Top.Value = 4, Right.Count = 2, Left.Count = 4
RotateLeft @value=6
LastValue = 7, Top.Value = 4, Right.Count = 3, Left.Count = 4
LastValue = 8, Top.Value = 4, Right.Count = 4, Left.Count = 4
RotateLeft @value=8
RotateLeft @value=7
LastValue = 9, Top.Value = 4, Right.Count = 5, Left.Count = 4
LastValue = 10, Top.Value = 4, Right.Count = 6, Left.Count = 4
RotateLeft @value=10
RotateLeft @value=9
RotateLeft @value=5
RotateLeft @value=4
LastValue = 11, Top.Value = 11, Right.Count = 0, Left.Count = 11
LastValue = 12, Top.Value = 11, Right.Count = 1, Left.Count = 11
RotateLeft @value=12
LastValue = 13, Top.Value = 11, Right.Count = 2, Left.Count = 11
RotateLeft @value=13
LastValue = 14, Top.Value = 11, Right.Count = 3, Left.Count = 11
LastValue = 15, Top.Value = 11, Right.Count = 4, Left.Count = 11
RotateLeft @value=15
RotateLeft @value=14
LastValue = 16, Top.Value = 11, Right.Count = 5, Left.Count = 11
LastValue = 17, Top.Value = 11, Right.Count = 6, Left.Count = 11
RotateLeft @value=17
LastValue = 18, Top.Value = 11, Right.Count = 7, Left.Count = 11
LastValue = 19, Top.Value = 11, Right.Count = 8, Left.Count = 11
RotateLeft @value=19
LastValue = 20, Top.Value = 11, Right.Count = 9, Left.Count = 11
LastValue = 21, Top.Value = 11, Right.Count = 10, Left.Count = 11
RotateLeft @value=21
LastValue = 22, Top.Value = 11, Right.Count = 11, Left.Count = 11
RotateLeft @value=22
RotateLeft @value=20
RotateLeft @value=18
LastValue = 23, Top.Value = 11, Right.Count = 12, Left.Count = 11
LastValue = 24, Top.Value = 11, Right.Count = 13, Left.Count = 11
LastValue = 25, Top.Value = 11, Right.Count = 14, Left.Count = 11
RotateLeft @value=25
RotateLeft @value=24
LastValue = 26, Top.Value = 11, Right.Count = 15, Left.Count = 11
LastValue = 27, Top.Value = 11, Right.Count = 16, Left.Count = 11
RotateLeft @value=27
LastValue = 28, Top.Value = 11, Right.Count = 17, Left.Count = 11
RotateLeft @value=28
RotateLeft @value=26
RotateLeft @value=23
RotateLeft @value=16
RotateLeft @value=11
LastValue = 29, Top.Value = 29, Right.Count = 0, Left.Count = 29
LastValue = 30, Top.Value = 29, Right.Count = 1, Left.Count = 29
LastValue = 31, Top.Value = 29, Right.Count = 2, Left.Count = 29
LastValue = 32, Top.Value = 29, Right.Count = 3, Left.Count = 29
RotateLeft @value=32
RotateLeft @value=31
LastValue = 33, Top.Value = 29, Right.Count = 4, Left.Count = 29
RotateLeft @value=33
RotateLeft @value=30
LastValue = 34, Top.Value = 29, Right.Count = 5, Left.Count = 29
RotateLeft @value=34
LastValue = 35, Top.Value = 29, Right.Count = 6, Left.Count = 29
LastValue = 36, Top.Value = 29, Right.Count = 7, Left.Count = 29
LastValue = 37, Top.Value = 29, Right.Count = 8, Left.Count = 29
RotateLeft @value=37
LastValue = 38, Top.Value = 29, Right.Count = 9, Left.Count = 29
LastValue = 39, Top.Value = 29, Right.Count = 10, Left.Count = 29
RotateLeft @value=39
LastValue = 40, Top.Value = 29, Right.Count = 11, Left.Count = 29
RotateLeft @value=40
RotateLeft @value=38
RotateLeft @value=36
LastValue = 41, Top.Value = 29, Right.Count = 12, Left.Count = 29
LastValue = 42, Top.Value = 29, Right.Count = 13, Left.Count = 29
RotateLeft @value=42
LastValue = 43, Top.Value = 29, Right.Count = 14, Left.Count = 29
LastValue = 44, Top.Value = 29, Right.Count = 15, Left.Count = 29
RotateLeft @value=44
LastValue = 45, Top.Value = 29, Right.Count = 16, Left.Count = 29
LastValue = 46, Top.Value = 29, Right.Count = 17, Left.Count = 29
RotateLeft @value=46
RotateLeft @value=45
LastValue = 47, Top.Value = 29, Right.Count = 18, Left.Count = 29
LastValue = 48, Top.Value = 29, Right.Count = 19, Left.Count = 29
LastValue = 49, Top.Value = 29, Right.Count = 20, Left.Count = 29

注文されたアイテムは、当然、ツリーの右側に常に追加されます。右側が左側よりも大きくなると、rotateleft が発生します。Rotateright は発生しません。ツリーが 2 倍になるたびに、新しいトップ ノードが選択されます。プライオリティ値のランダム性が少し乱れるため、この実行では 0、1、4、11、29 になります。

ランダムに実行すると、興味深いことが明らかになります。

TimeIt(50, RandomInsert)
LastValue = 0,748661640914465, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 0
LastValue = 0,669427539533669, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 1
RotateRight @value=0,669427539533669
LastValue = 0,318363281115127, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 2
RotateRight @value=0,669427539533669
LastValue = 0,33133987678743, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 3
RotateLeft @value=0,748661640914465
LastValue = 0,955126694382693, Top.Value = 0,955126694382693, Right.Count = 0, Left.Count = 4
RotateRight @value=0,669427539533669
RotateLeft @value=0,33133987678743
RotateLeft @value=0,318363281115127
RotateRight @value=0,748661640914465
RotateRight @value=0,955126694382693
LastValue = 0,641024029180884, Top.Value = 0,641024029180884, Right.Count = 3, Left.Count = 2
LastValue = 0,20709771951991, Top.Value = 0,641024029180884, Right.Count = 3, Left.Count = 3
LastValue = 0,830862050331599, Top.Value = 0,641024029180884, Right.Count = 4, Left.Count = 3
RotateRight @value=0,20709771951991
RotateRight @value=0,318363281115127
LastValue = 0,203250563798123, Top.Value = 0,641024029180884, Right.Count = 4, Left.Count = 4
RotateLeft @value=0,669427539533669
RotateRight @value=0,748661640914465
RotateRight @value=0,955126694382693
LastValue = 0,701743399585478, Top.Value = 0,641024029180884, Right.Count = 5, Left.Count = 4
RotateLeft @value=0,669427539533669
RotateRight @value=0,701743399585478
RotateLeft @value=0,641024029180884
LastValue = 0,675667521858433, Top.Value = 0,675667521858433, Right.Count = 4, Left.Count = 6
RotateLeft @value=0,33133987678743
RotateLeft @value=0,318363281115127
RotateLeft @value=0,203250563798123
LastValue = 0,531275219531392, Top.Value = 0,675667521858433, Right.Count = 4, Left.Count = 7
RotateRight @value=0,748661640914465
RotateRight @value=0,955126694382693
RotateLeft @value=0,701743399585478
LastValue = 0,704049674190604, Top.Value = 0,675667521858433, Right.Count = 5, Left.Count = 7
RotateRight @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
LastValue = 0,161392807104342, Top.Value = 0,161392807104342, Right.Count = 13, Left.Count = 0
RotateRight @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateLeft @value=0,161392807104342
LastValue = 0,167598206162266, Top.Value = 0,167598206162266, Right.Count = 13, Left.Count = 1
LastValue = 0,154996359793002, Top.Value = 0,167598206162266, Right.Count = 13, Left.Count = 2
RotateLeft @value=0,33133987678743
LastValue = 0,431767346538495, Top.Value = 0,167598206162266, Right.Count = 14, Left.Count = 2
RotateRight @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateLeft @value=0,167598206162266
LastValue = 0,173774613614089, Top.Value = 0,173774613614089, Right.Count = 14, Left.Count = 3
RotateRight @value=0,830862050331599
LastValue = 0,76559642412029, Top.Value = 0,173774613614089, Right.Count = 15, Left.Count = 3
RotateRight @value=0,76559642412029
RotateLeft @value=0,748661640914465
RotateRight @value=0,955126694382693
RotateLeft @value=0,704049674190604
RotateLeft @value=0,675667521858433
LastValue = 0,75742144871383, Top.Value = 0,173774613614089, Right.Count = 16, Left.Count = 3
LastValue = 0,346844367844446, Top.Value = 0,173774613614089, Right.Count = 17, Left.Count = 3
RotateRight @value=0,830862050331599
LastValue = 0,787565814232251, Top.Value = 0,173774613614089, Right.Count = 18, Left.Count = 3
LastValue = 0,734950566540915, Top.Value = 0,173774613614089, Right.Count = 19, Left.Count = 3
RotateLeft @value=0,20709771951991
RotateRight @value=0,318363281115127
RotateLeft @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateRight @value=0,75742144871383
RotateLeft @value=0,173774613614089
LastValue = 0,236504829598826, Top.Value = 0,236504829598826, Right.Count = 17, Left.Count = 6
RotateLeft @value=0,830862050331599
RotateLeft @value=0,787565814232251
RotateLeft @value=0,76559642412029
RotateRight @value=0,955126694382693
LastValue = 0,895606500048007, Top.Value = 0,236504829598826, Right.Count = 18, Left.Count = 6
LastValue = 0,599106418713511, Top.Value = 0,236504829598826, Right.Count = 19, Left.Count = 6
LastValue = 0,8182332901369, Top.Value = 0,236504829598826, Right.Count = 20, Left.Count = 6
RotateRight @value=0,734950566540915
LastValue = 0,704216948572647, Top.Value = 0,236504829598826, Right.Count = 21, Left.Count = 6
RotateLeft @value=0,346844367844446
RotateLeft @value=0,33133987678743
RotateRight @value=0,431767346538495
RotateLeft @value=0,318363281115127
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateRight @value=0,75742144871383
LastValue = 0,379157059536854, Top.Value = 0,236504829598826, Right.Count = 22, Left.Count = 6
RotateLeft @value=0,431767346538495
LastValue = 0,46832062046431, Top.Value = 0,236504829598826, Right.Count = 23, Left.Count = 6
RotateRight @value=0,154996359793002
LastValue = 0,0999000217299443, Top.Value = 0,236504829598826, Right.Count = 23, Left.Count = 7
RotateLeft @value=0,20709771951991
LastValue = 0,229543754006524, Top.Value = 0,236504829598826, Right.Count = 23, Left.Count = 8
RotateRight @value=0,8182332901369
LastValue = 0,80358425984326, Top.Value = 0,236504829598826, Right.Count = 24, Left.Count = 8
RotateRight @value=0,318363281115127
LastValue = 0,259324726769386, Top.Value = 0,236504829598826, Right.Count = 25, Left.Count = 8
RotateRight @value=0,318363281115127
LastValue = 0,307835293145774, Top.Value = 0,236504829598826, Right.Count = 26, Left.Count = 8
RotateLeft @value=0,431767346538495
LastValue = 0,453910283024381, Top.Value = 0,236504829598826, Right.Count = 27, Left.Count = 8
RotateLeft @value=0,830862050331599
LastValue = 0,868997387527021, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 8
RotateLeft @value=0,20709771951991
RotateRight @value=0,229543754006524
RotateLeft @value=0,203250563798123
LastValue = 0,218358597354199, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 9
RotateRight @value=0,0999000217299443
RotateRight @value=0,161392807104342
LastValue = 0,0642934488431986, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 10
RotateRight @value=0,154996359793002
RotateLeft @value=0,0999000217299443
LastValue = 0,148295871982489, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 11
LastValue = 0,217621828065078, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 12
RotateRight @value=0,599106418713511
LastValue = 0,553135806020878, Top.Value = 0,236504829598826, Right.Count = 29, Left.Count = 12
LastValue = 0,982277666210326, Top.Value = 0,236504829598826, Right.Count = 30, Left.Count = 12
RotateRight @value=0,8182332901369
LastValue = 0,803671114520948, Top.Value = 0,236504829598826, Right.Count = 31, Left.Count = 12
RotateRight @value=0,203250563798123
RotateRight @value=0,218358597354199
LastValue = 0,19310415405459, Top.Value = 0,236504829598826, Right.Count = 31, Left.Count = 13
LastValue = 0,0133136604043253, Top.Value = 0,236504829598826, Right.Count = 31, Left.Count = 14
RotateLeft @value=0,46832062046431
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateRight @value=0,75742144871383
LastValue = 0,483394719419719, Top.Value = 0,236504829598826, Right.Count = 32, Left.Count = 14
RotateLeft @value=0,431767346538495
RotateRight @value=0,453910283024381
LastValue = 0,453370328738061, Top.Value = 0,236504829598826, Right.Count = 33, Left.Count = 14
LastValue = 0,762330518459124, Top.Value = 0,236504829598826, Right.Count = 34, Left.Count = 14
LastValue = 0,699010426969738, Top.Value = 0,236504829598826, Right.Count = 35, Left.Count = 14

ツリーのバランスが取れていないため、ローテーションはあまり発生しませんが、ランダムに選択される優先順位のために発生します。たとえば、13 回目の挿入で 4 回転します。ツリーは 5/7 (これで問題ありません) でバランスが取れていますが、13/0 になります! ランダムな優先順位の使用については、さらに調査する価値があるようです。とにかく、ランダムな挿入が順序付けられた挿入よりも多くの回転を引き起こすことは明らかです。

Answer 2

非ランダム分散データに関連する問題を修正するために、自己均衡ツリーが存在します。定義上、それらは最良の場合のパフォーマンスを少し犠牲にして、バランスの取れていない BST、特にソートされた入力に関連する最悪の場合のパフォーマンスを大幅に改善します。

ランダムデータと順序付けられたデータの挿入が遅いのはバランスの取れたツリーの特徴であるため、実際にはこの問題を考えすぎています。AVL で試してみると、同じ結果が得られます。

Cameronは正しい考えを持っていて、最悪のケースを強制するために優先度チェックを削除しました。これを実行してツリーをインストルメント化し、挿入ごとにリバランスが何回発生しているかを確認できるようにすると、実際に何が起こっているかが非常に明確になります。ソートされたデータを挿入すると、ツリーは常に左に回転し、ルートの右の子は常に空になります。挿入ノードには子がなく、再帰が発生しないため、挿入は常に 1 回のリバランスになります。一方、ランダムなデータで実行すると、すべての挿入で複数のリバランスが発生しているのがすぐにわかります。最小のケース (50 回の挿入) では 5 ～ 6 回です。良い。

優先度チェックをオンに戻すと、より多くのノードが左側のサブツリー (そこでは挿入が行われないため、そこから出ることはありません) にプッシュされるため、リバランスのコストが通常低くなるだけでなく、それらが発生する可能性も低くなります。なんで？トレプでは、優先度の高いノードが一番上に浮かび、一定の左回転 (右回転を伴わない) により、すべての優先度の高いノードが左側のサブツリーにもプッシュされ始めるためです。その結果、確率が不均一に分布するため、リバランスの頻度が低くなります。

リバランス コードを計測すると、これが正しいことがわかります。ソートされた入力とランダム入力の両方で、最終的にはほぼ同じ数の左回転になりますが、ランダム入力でも同じ数の右回転が得られ、全体で 2 倍になります。これは驚くべきことではありません - ガウス入力は回転のガウス分布になるはずです。また、並べ替えられた入力の最上位レベルのリバランスが約 60 ～ 70% しかないこともわかります。これはおそらく驚くべきことです。これは、並べ替えられた入力が優先順位の自然な分布を混乱させているためです。

これは、挿入ループの最後でツリー全体を検査することによっても確認できます。ランダムな入力では、優先度はレベルごとにかなり直線的に減少する傾向があります。並べ替えられた入力では、下から 1 つまたは 2 つのレベルに到達するまで、優先順位は非常に高いままになる傾向があります。

これについてうまく説明できていることを願っています。あいまいすぎる場合はお知らせください。

Answer 3

標準偏差の計算を追加し、テストを最高の優先度で実行するように変更しました (可能な限りノイズを減らすため)。結果は次のとおりです。

Random                                   Ordered
0,2835 (stddev 0,9946)                   0,0891 (stddev 0,2372)
0,1230 (stddev 0,0086)                   0,0780 (stddev 0,0031)
0,2498 (stddev 0,0662)                   0,1694 (stddev 0,0145)
0,5136 (stddev 0,0441)                   0,3550 (stddev 0,0658)
1,1704 (stddev 0,1072)                   0,6632 (stddev 0,0856)
1,4672 (stddev 0,1090)                   0,8343 (stddev 0,1047)
3,3330 (stddev 0,2041)                   1,9272 (stddev 0,3456)
7,9822 (stddev 0,3906)                   3,7871 (stddev 0,1459)
18,4300 (stddev 0,6112)                  10,3233 (stddev 2,0247)
44,9500 (stddev 2,2935)                  22,3870 (stddev 1,7157)
110,5275 (stddev 3,7129)                 49,4085 (stddev 2,9595)
275,4345 (stddev 10,7154)                107,8442 (stddev 8,6200)
667,7310 (stddev 20,0729)                242,9779 (stddev 14,4033)

サンプリング プロファイラーを実行しました。結果は次のとおりです (プログラムがこのメソッドにあった回数)。

Method           Random        Ordered
HeapifyRight()   1.95          5.33
get_IsEmpty()    3.16          5.49
Make()           3.28          4.92
Insert()         16.01         14.45
HeapifyLeft()    2.20          0.00

結論: 乱数は左回転と右回転の間にかなり合理的な分布を持ちますが、順序付きは決して左回転しません。

これが私の改良された「ベンチマーク」プログラムです。

    static void Main(string[] args)
    {
        Thread.CurrentThread.Priority = ThreadPriority.Highest;
        Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.RealTime;

        List<String> rndTimes = new List<String>();
        List<String> orderedTimes = new List<String>();

        rndTimes.Add(TimeIt(50, RandomInsert));
        rndTimes.Add(TimeIt(100, RandomInsert));
        rndTimes.Add(TimeIt(200, RandomInsert));
        rndTimes.Add(TimeIt(400, RandomInsert));
        rndTimes.Add(TimeIt(800, RandomInsert));
        rndTimes.Add(TimeIt(1000, RandomInsert));
        rndTimes.Add(TimeIt(2000, RandomInsert));
        rndTimes.Add(TimeIt(4000, RandomInsert));
        rndTimes.Add(TimeIt(8000, RandomInsert));
        rndTimes.Add(TimeIt(16000, RandomInsert));
        rndTimes.Add(TimeIt(32000, RandomInsert));
        rndTimes.Add(TimeIt(64000, RandomInsert));
        rndTimes.Add(TimeIt(128000, RandomInsert));
        orderedTimes.Add(TimeIt(50, OrderedInsert));
        orderedTimes.Add(TimeIt(100, OrderedInsert));
        orderedTimes.Add(TimeIt(200, OrderedInsert));
        orderedTimes.Add(TimeIt(400, OrderedInsert));
        orderedTimes.Add(TimeIt(800, OrderedInsert));
        orderedTimes.Add(TimeIt(1000, OrderedInsert));
        orderedTimes.Add(TimeIt(2000, OrderedInsert));
        orderedTimes.Add(TimeIt(4000, OrderedInsert));
        orderedTimes.Add(TimeIt(8000, OrderedInsert));
        orderedTimes.Add(TimeIt(16000, OrderedInsert));
        orderedTimes.Add(TimeIt(32000, OrderedInsert));
        orderedTimes.Add(TimeIt(64000, OrderedInsert));
        orderedTimes.Add(TimeIt(128000, OrderedInsert));
        var result = string.Join("\n", (from s in rndTimes
                        join s2 in orderedTimes
                            on rndTimes.IndexOf(s) equals orderedTimes.IndexOf(s2)
                        select String.Format("{0} \t\t {1}", s, s2)).ToArray());
        Console.WriteLine(result);
        Console.WriteLine("Done");
        Console.ReadLine();
    }

    static double StandardDeviation(List<double> doubleList)
    {
        double average = doubleList.Average();
        double sumOfDerivation = 0;
        foreach (double value in doubleList)
        {
            sumOfDerivation += (value) * (value);
        }
        double sumOfDerivationAverage = sumOfDerivation / doubleList.Count;
        return Math.Sqrt(sumOfDerivationAverage - (average * average));
    }
    static String TimeIt(int insertCount, Action<int> f)
    {
        Console.WriteLine("TimeIt({0}, {1})", insertCount, f.Method.Name);

        List<double> times = new List<double>();
        for (int i = 0; i < ITERATION_COUNT; i++)
        {
            Stopwatch sw = Stopwatch.StartNew();
            f(insertCount);
            sw.Stop();
            times.Add(sw.Elapsed.TotalMilliseconds);
        }

        return String.Format("{0:f4} (stddev {1:f4})", times.Average(), StandardDeviation(times));
    }

Answer 4

約 2 倍の違いしか見られません。このコードから昼光を調整していない限り、それは基本的に騒音の中にあります。ほとんどの適切に作成されたプログラム、特にデータ構造を含むプログラムには、それよりも改善の余地が簡単にある可能性があります。これが例です。

コードを実行して、いくつかのスタックショットを撮りました。これが私が見たものです：

ランダム挿入:

1 Insert:64 -> HeapifyLeft:81 -> RotateRight:150
1 Insert:64 -> Make:43 ->Treap:35
1 Insert:68 -> Make:43

順序付き挿入:

1 Insert:61
1 OrderedInsert:224
1 Insert:68 -> Make:43
1 Insert:68 -> HeapifyRight:90 -> RotateLeft:107
1 Insert:68
1 Insert:68 -> Insert:55 -> IsEmpty.get:51

これはかなり少数のサンプルですが、ランダムな入力の場合、Make (43 行目) がより多くの時間を消費していることを示唆しています。それがこのコードです:

    private Treap<T> Make(Treap<T> left, T value, Treap<T> right, int priority)
    {
        return new Treap<T>(Comparer, left, value, right, priority);
    }

次に、Random Insert コードのスタックショットを 20 枚撮って、それが何をしているのかをよりよく理解しました。

1 Insert:61
4 Insert:64
3 Insert:68
2 Insert:68 -> Make:43
1 Insert:64 -> Make:43
1 Insert:68 -> Insert:57 -> Make:48 -> Make:43
2 Insert:68 -> Insert:55
1 Insert:64 -> Insert:55
1 Insert:64 -> HeapifyLeft:81 -> RotateRight:150
1 Insert:64 -> Make:43 -> Treap:35
1 Insert:68 -> HeapifyRight:90 -> RotateLeft:107 -> IsEmpty.get:51
1 Insert:68 -> HeapifyRight:88
1 Insert:61 -> AnonymousMethod:214

これにより、いくつかの情報が明らかになります。
25% の時間は Make:43 またはその呼び出し先で費やされます。
時間の 15% は、認識されたルーチンではなく、その行、つまりnew新しいノードの作成に費やされます。
時間の 90% は行 Insert:64 と 68 (Make と heapify を呼び出す) で費やされます。
時間の 10% は RotateLeft と Right で費やされます。
時間の 15% は Heapify またはその呼び出し先で費やされます。

また、(ソース レベルで) かなりの量のシングル ステップを行ったところ、ツリーは不変であるため、古いノードを変更したくないため、新しいノードの作成に多くの時間を費やしているのではないかと疑うようになりました。その後、古いものはガベージ コレクションされます。

これは非効率でなければなりません。

順序付けられた数値を挿入する方がランダムに生成された数値よりも速い理由についての質問にはまだ答えていませんが、ツリーは不変であるため、それほど驚くことではありません。

ツリー アルゴリズムに関するパフォーマンスの推論が不変ツリーに簡単に引き継がれるとは期待できないと思います。ツリーの奥深くにあるわずかな変更により、途中で再構築され、new-ing とガベージのコストが高くなるためです。コレクション。

Answer 5

はい、余分な時間を引き起こしているのは回転数です。これが私がしたことです：

• 優先度をチェックする行を削除するHeapifyLeftとHeapifyRight、常にローテーションが行われます。
• とConsole.WriteLineの ifの後に を追加しました。RotateLeftRotateRight
• Console.WriteLineメソッドのIsEmpty一部にa を追加して、Insert何が挿入されているかを確認しました。
• それぞれ 5 つの値でテストを 1 回実行します。

出力：

TimeIt(5, RandomInsert)
Inserting 0.593302943554382
Inserting 0.348900582338171
RotateRight
Inserting 0.75496212381635
RotateLeft
RotateLeft
Inserting 0.438848891499848
RotateRight
RotateLeft
RotateRight
Inserting 0.357057290783644
RotateLeft
RotateRight

TimeIt(5, OrderedInsert)
Inserting 0.150707998383189
Inserting 1.58281302712057
RotateLeft
Inserting 2.23192588297274
RotateLeft
Inserting 3.30518679009061
RotateLeft
Inserting 4.32788012657682
RotateLeft

結果: ランダム データの 2 倍の回転数。

Answer 6

@Gugeは正しいです。しかし、それにはもう少しだけがあります。この場合、それが最大の要因であると言っているわけではありませんが、そこにあり、それについて何もするのは難しいです.

ソートされた入力の場合、ルックアップはキャッシュ内でホットなノードにアクセスする可能性があります。(これは一般に、AVL ツリー、赤黒ツリー、B ツリーなどのバランスの取れたツリーに当てはまります。)

挿入はルックアップで始まるため、これは挿入/削除のパフォーマンスにも影響します。

繰り返しますが、すべてのケースにおいて、それが最も重要な要因であると主張しているわけではありません。ただし、これらのデータ構造では、並べ替えられた入力がランダムな入力よりも常に高速になる可能性があります。

Answer 7

Aaronaught has done a really decent job explaining this.

For these two special cases, I find it easier to grasp it in terms of the insertion path lengths.

For random input, your insertion path goes down to one of the leaves and the length of the path - thus the number of rotations - are bounded by the height of the tree.

In the sorted case, you walk on the right spine of the treap and the bound is the length of the spine, which is less than or equal to the the height.

Since you rotate nodes along the insertion path and your insertion path is the spine in this case, these rotations will always shorten the spine (which will result in a shorter insertion path at the next insertion, since the insertion path is just the spine etc.)

Edit: for the random case the insertion path is 1.75x longer.

Answer 8

これを試してください: trap のデータベース。

http://code.google.com/p/treapdb/