问题描述
我只是做对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的这个巨大的性能差异的原因的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！