本文介绍了什么是落后于.NET 4的这个巨大的性能差异的原因的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我只是做对RedBlack树一些研究。我知道,在.NET 4.0中的SortedSet类使用RedBlack树。所以我把该部分出如使用反射,创造了RedBlackTree类。现在,我正在对这个RedBlackTree一些PERF的测试和SortedSet的插入顺序40000积分值(从0到39999),我很惊讶地看到,有巨大的PERF的区别如下:

I was just doing some research on RedBlack Tree. I knew that SortedSet class in .Net 4.0 uses RedBlack tree. So I took that part out as is using Reflector and created a RedBlackTree class. Now I am running some perf test on this RedBlackTree and SortedSet inserting 40000 sequential integral values (starting from 0 to 39999), I am astonished to see that there is huge perf difference as follows:

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

这是什么背后的原因是什么?顺便说一句我跑的测试只发布配置和这里是小试code

What is the reason behind it? BTW I ran the test in Release configuration only and here is the small test code

            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);

修改

我也想分享$ C $下RBTree我所提取的,这样你也可以运行诊断

I would like to share the code also for RBTree what I've extracted so that you also can run the diagnostics

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;
            }
        }
    }


修改


Edit

我跑了相同的诊断上的其他一些数据结构(由我创造了一些*,有的从.NET框架**),这里是一个有趣的结果。

I ran the same diagnostic on some other data structure (some created by me*, some from .net framework**) and here is the interesting results

*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类剥离出来)。 我试着用40万也值,但RBTree似乎到永远,我真的不知道为什么。

RBTree is the same as above (stripped out from SortedSet class). I tried with 400000 values also, but RBTree seems taking FOREVER, I really don't know why.

推荐答案

您的节点&lt错误; T&GT; 类。当调用构造函数只需要一个值的参数,你应该设置 IsRed

You have a bug in your Node<T> class. When you call the constructor that only takes a single value argument you should be setting IsRed to true.

我想,固定节点&lt; T&GT; 类应该是这个样子:

I suppose that the fixed Node<T> class should look something like this:

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;
    }
}

另一种选择 - 我的preference - 将是完全省略构造和总是需要 IsRed 来显式设置,当你实例化一个新的节点:

Another option -- my preference -- would be to omit that constructor altogether and always require IsRed to be set explicitly when you instantiate a new node:

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;
    }
}

,然后替换该行的添加方法...

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

...这个...

...with this...

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

这篇关于什么是落后于.NET 4的这个巨大的性能差异的原因的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-06 06:07