Я просто занимался исследованиями RedBlack Tree. Я знал, что класс SortedSet в .Net 4.0 использует дерево 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
В чем причина этого? BTW Я проверил тест только в конфигурации Release и вот небольшой тестовый код
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 framework **), и вот интересные результаты
*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, я действительно не знаю почему.
