18

RedBlack Tree について調査していたところです。.Net 4.0 の SortedSet クラスが RedBlack ツリーを使用していることは知っていました。そこで、Reflector を使ってその部分をそのまま取り出して、RedBlackTree クラスを作成しました。今、この RedBlackTree と SortedSet に 40000 の連続した整数値 (0 から 39999 まで) を挿入していくつかのパフォーマンス テストを実行しています。次のように大きなパフォーマンスの違いがあることに驚いています。

 RBTree    took 9.27208   sec to insert 40000 values 
 SortedSet took 0.0253097 sec to insert 40000 values

その背後にある理由は何ですか？ところで、リリース構成のみでテストを実行しました。ここに小さなテストコードがあります

            var stopWatch = new Stopwatch();
            var rbT = new RedBlackTree<int>();      
        stopWatch = new Stopwatch();
        stopWatch.Start();
        for (int i = 0; i < 40000; i++) {
            rbT.Add(i);
        }
        stopWatch.Stop();
        Console.WriteLine(stopWatch.Elapsed);

        var ss = new SortedSet<int>();
        stopWatch = new Stopwatch();
        stopWatch.Start();
        for (int i = 0; i < 40000; i++) {
            ss.Add(i);
        }
        stopWatch.Stop();
        Console.WriteLine(stopWatch.Elapsed);

編集

抽出した RBTree のコードも共有して、診断を実行できるようにしたいと思います。

public class Node<T>
    {
        public Node(){}

        public Node(T value)
        {
            Item = value;
        }       

        public Node(T value, bool isRed)
        {
            Item = value;
            IsRed = isRed;
        }

        public T Item;
        public Node<T> Left;
        public Node<T> Right;
        public Node<T> Parent;
        public bool IsRed;
    }

    public class RedBlackTree<T>
    {
        public RedBlackTree(){} 

        public Node<T> root;
        int count, version; 
        Comparer<T> comparer = Comparer<T>.Default;     

        public void Add(T item)
        {
            if (this.root == null)
            {
                this.root = new Node<T>(item, false);
                this.count = 1;
                this.version++;
                return;
            }

            Node<T> root = this.root;
            Node<T> node = null;
            Node<T> grandParent = null;
            Node<T> greatGrandParent = null;
            this.version++;

            int num = 0;
            while (root != null)
            {
                num = this.comparer.Compare(item, root.Item);
                if (num == 0)
                {
                    this.root.IsRed = false;
                    return;
                }
                if (Is4Node(root))
                {
                    Split4Node(root);
                    if (IsRed(node))
                    {
                        this.InsertionBalance(root, ref node, grandParent, greatGrandParent);
                    }
                }
                greatGrandParent = grandParent;
                grandParent = node;
                node = root;
                root = (num < 0) ? root.Left : root.Right;
            }
            Node<T> current = new Node<T>(item);
            if (num > 0)
            {
                node.Right = current;
            }
            else
            {
                node.Left = current;
            }
            if (node.IsRed)
            {
                this.InsertionBalance(current, ref node, grandParent, greatGrandParent);
            }
            this.root.IsRed = false;
            this.count++;
        }


        private static bool IsRed(Node<T> node)
        {
            return ((node != null) && node.IsRed);
        }

        private static bool Is4Node(Node<T> node)
        {
            return (IsRed(node.Left) && IsRed(node.Right));
        }

        private static void Split4Node(Node<T> node)
        {
            node.IsRed = true;
            node.Left.IsRed = false;
            node.Right.IsRed = false;
        }

        private void InsertionBalance(Node<T> current, ref Node<T> parent, Node<T> grandParent, Node<T> greatGrandParent)
        {
            Node<T> node;
            bool flag = grandParent.Right == parent;
            bool flag2 = parent.Right == current;
            if (flag == flag2)
            {
                node = flag2 ? RotateLeft(grandParent) : RotateRight(grandParent);
            }
            else
            {
                node = flag2 ? RotateLeftRight(grandParent) : RotateRightLeft(grandParent);
                parent = greatGrandParent;
            }
            grandParent.IsRed = true;
            node.IsRed = false;
            ReplaceChildOfNodeOrRoot(greatGrandParent, grandParent, node);
        }

        private static Node<T> RotateLeft(Node<T> node)
        {
            Node<T> right = node.Right;
            node.Right = right.Left;
            right.Left = node;
            return right;
        }

        private static Node<T> RotateRight(Node<T> node)
        {
            Node<T> left = node.Left;
            node.Left = left.Right;
            left.Right = node;
            return left;
        }

        private static Node<T> RotateLeftRight(Node<T> node)
        {
            Node<T> left = node.Left;
            Node<T> right = left.Right;
            node.Left = right.Right;
            right.Right = node;
            left.Right = right.Left;
            right.Left = left;
            return right;
        }

        private static Node<T> RotateRightLeft(Node<T> node)
        {
            Node<T> right = node.Right;
            Node<T> left = right.Left;
            node.Right = left.Left;
            left.Left = node;
            right.Left = left.Right;
            left.Right = right;
            return left;
        }

        private void ReplaceChildOfNodeOrRoot(Node<T> parent, Node<T> child, Node<T> newChild)
        {
            if (parent != null)
            {
                if (parent.Left == child)
                {
                    parent.Left = newChild;
                }
                else
                {
                    parent.Right = newChild;
                }
            }
            else
            {
                this.root = newChild;
            }
        }
    }

編集

他のデータ構造（私が作成したもの*、.netフレームワーク**からのもの）で同じ診断を実行したところ、興味深い結果が得られました

*AATree                 00:00:00.0309294
*AVLTree                00:00:00.0129743
**SortedDictionary      00:00:00.0313571
*RBTree                 00:00:09.2414156
**SortedSet             00:00:00.0241973

RBTree は上記と同じです (SortedSet クラスから取り除かれています)。私も 400000 の値で試しましたが、RBTree は FOREVER を取っているようです。理由は本当にわかりません。

4

4 に答える 4

17

Node<T>クラスにバグがあります。単一の値の引数のみを取るコンストラクターを呼び出すときは、に設定IsRedする必要がありますtrue。

固定Node<T>クラスは次のようになるはずです。

public sealed class Node<T>
{
    public T Item { get; private set; }
    public bool IsRed { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }

    public Node(T value)
    {
        Item = value;
        IsRed = true;
    }

    public Node(T value, bool isRed)
    {
        Item = value;
        IsRed = isRed;
    }
}

別のオプション - 私の好み - は、そのコンストラクターを完全に省略しIsRed、新しいノードをインスタンス化するときに常に明示的に設定する必要があります。

public sealed class Node<T>
{
    public T Item { get; private set; }
    public bool IsRed { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }

    public Node(T value, bool isRed)
    {
        Item = value;
        IsRed = isRed;
    }
}

そして、あなたのAddメソッドでこの行を置き換えてください...

Node<T> current = new Node<T>(item);

...これとともに...

Node<T> current = new Node<T>(item, true);
于 2010-09-15T11:07:04.677 に答える
3
  1. テストの順序を逆にして、測定を繰り返します。
  2. データをランダム化します。事前に並べ替えられたデータを挿入すると、並べ替えられたセットが奇妙な動作をします。
于 2010-09-15T08:41:00.190 に答える
1

SortedSet にはTargetedPatchingOptOut属性が含まれていますが、コピーしたバージョンにはそれが含まれていましたか?

[TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")]
public bool Add(T item)
{
    return this.AddIfNotPresent(item);
}
于 2010-09-15T08:19:29.457 に答える
0

違いがそれほど大きくない場合、原因は .NET アセンブリが NGen 化されているため、既にネイティブ コードに変換されていることです。クラスの場合、IL コードをネイティブ コードにコンパイルする時間は、テストの時間で償却されます。ループの反復回数を増やすと、時間にどのような影響がありますか?

于 2010-09-15T08:04:14.403 に答える