Saf*_*ron 5 c# avl-tree binary-search-tree data-structures
想象一下,我有一个很大的整数排序列表(> 1000项).我需要能够在此列表上执行两个操作:删除下半部分并通过插入随机整数将列表再次填充到其原始大小.因为我做了大约一百万次这些操作,所以我需要它尽可能高效.
我做的第一件事就是使用List我通过在正确的位置添加新项目进行排序的方法.虽然删除排序列表的下半部分非常容易,但插入需要相当长的时间.
我尝试实现一个跳过列表,但经过一些测试后,列表的大小似乎必须至少为10000才真正重要,否则它的表现甚至比我的正常列表更糟糕.
这就是为什么我决定使用AVL树,所以我可以更快,更快地插入项目.但问题是我不知道删除这种二叉搜索树的下半部分的任何有效方法.
我的问题是:有没有一种有效的方法来做到这一点？还有其他我可以更轻松使用的数据结构吗？
如上所述,我做了一个小测试,显示了列表,跳过列表和AVL树之间的性能差异.我在msdn:Skip list tutorial上使用本教程制作了跳过列表.AVL树来自这里:AVL树.我在dropbox上传了测试:示例.还有关于pastebin:程序.
在测试中,我在计时时为每个数据结构添加了10万个项目.在我的电脑上,列表大约需要1秒,跳过列表需要0.5秒,AVL树需要0.045秒.如果我按照我的意愿做了一百万次,那么这个列表大约需要11.5天,但AVL树只需要大约半天.这个时间差异清楚地表明了我希望它有效的原因.
关于这个问题,我想指出一些问题.首先,让我们直截了当地谈谈性能和C#,因为在存在误解的情况下很难解释这些问题.
接下来,我将在这里将所有内容应用于具体问题.
C#中的性能一般
Big-O表示法
在大学里,你将学习O(n)总是优于O(n ^ 2)以及O(n)如何总是优于O(n log n).然而,对此的基本假设是每个操作将花费大致相同的时间量.
现在,当我在1986年第一次开始使用1802 RISC处理器进行编程时,情况就是如此:内存操作是1个时钟滴答,加法,减法等也是如此.换句话说,Big-O在那里工作得很好.
在现代计算机中,它更难:
我观察到同一算法的不同实现的性能差异可能高达1000倍(!)
Big-O仍然具有优点,但你应该把事情放在眼里.例如,假设你有N = 10000,那么2log N~13 - 如果这意味着你可以从所有这些事情中受益,那么它也可能意味着'愚蠢'的O(n log n)算法可能会胜过你的平均O(n)算法.
从这里你还应该推断出O(n ^ 2)不会胜过O(n)算法.所以,Big-O仍有其用途; 你只需要把事情放在眼里.
关于C#的一些特征
关于C#的一个神话是它与C++一样快(这是我"尽可能快"的黄金标准).在熟练的开发人员手中,它不是那么简单.对于简单的排序,C++的速度大约是2倍 - 但是如果你有更复杂的场景,你可以真正从"低级别的东西"中受益,那么差异就会变得非常大.我通常估计性能差异是因素10.然而,编写适当的高性能C++代码具有挑战性(使用轻描淡写),因此您可能希望坚持使用C#并决定将性能命中视为理所当然.
有一点感兴趣的是C#编译器和JIT编译的东西非常快.在某种程度上,这是因为他们编译了每个函数的所有内容(因此,没有内联等).此外,C#通常不会对内容进行矢量化.不要相信我的意思,在Visual Studio中使用ctrl-alt-d并自己检查汇编器输出.
如果我们查看上面的列表,我们可以粗略地说明(1),(2)和(3)不受我们使用C#这一事实的影响; (4)肯定受到影响,(5)取决于.
至于(5),请考虑这个简单的例子:
void set(int[] array, int index)
{
array[index] = 0;
}
请记住,在C#方法中是按方法编译的.这意味着编译器不能假设index不会超出范围.换句话说:它必须添加两个检查 - 其中一个必须加载内存:
if (index < 0 || index >= array.Length)
{
throw new IndexOutOfRangeException();
}
排序项目
OP的问题是关于维护一个排序的大小列表m.排序是一项众所周知的操作,O(log m)每次插入物品的成本最高.由于您正在处理n"随机"项目,因此您将获得最佳速度O(n log m).
二进制堆(基于数组)可能会获得性能数字,但我现在不想写下堆,并认为这种替代方法速度大致相同(如果不是更快):)
你的问题
现在我们已经建立了我们正在谈论的内容,让我们深入了解手头的事实.我将在每一步中解释这一点.
首先,在执行性能时,我习惯删除,using System.Linq因此我们知道我们只是处理具有预期特征的本机数据结构.
让我们从树结构开始
另一个简单的解决方案是使用红黑树.我们在.NET中有一个名为a的SortedSet.它使用引用,算术等 - 这基本上是我在(1),(2)和(3)中警告的所有令人讨厌的东西.现在,这里的实现中存在错误(对于重复),但速度几乎是您所期望的:
static void Main(string[] args)
{
Random rnd = new Random(12839);
SortedSet<int> list = new SortedSet<int>();
for (int i = 0; i < 5000; ++i)
{
list.Add(rnd.Next());
}
Stopwatch sw = Stopwatch.StartNew();
for (int i = 0; i < 10000; ++i)
{
for (int j = 0; j < 5000; ++j)
{
list.Add(rnd.Next());
}
int n = 0;
list.RemoveWhere((a) => n++ < 5000);
}
Console.WriteLine(sw.ElapsedMilliseconds);
Console.ReadLine();
}
像这里几乎所有的算法一样,这个算法执行O(n log m).
我对AVL树的期望是:86220 ms.
天真的实施
通常我不会对红黑树感到困扰.尽管如此,由于你在AVL树中投入了大量的工作,我觉得有必要进行这种测量.
当我正在对算法进行性能优化时,我总是从最容易实现的算法开始,该算法具有大致正确的Big-O并且总是更喜欢具有最简单数据结构的东西(读取:数组).在这种情况下,它是一个与标准排序相结合的列表,它将提供O(m log m)每种排序,执行m/n时间和O(n)数据操作.结果是O(n + n log m).
那么,为什么选择最简单的实现呢？答案很简单:易于实现也易于编译和优化,因为它们通常没有很多分支,不使用大量随机内存访问等.
最天真的实现(我在评论中已经提到过)是简单地将东西放入数组中,对其进行排序,然后删除它的下半部分.
基本上,这可以在最小的测试用例中实现:
static void Main(string[] args)
{
Random rnd = new Random(12839);
List<int> list = new List<int>();
for (int i = 0; i < 5000; ++i)
{
list.Add(rnd.Next());
}
Stopwatch sw = Stopwatch.StartNew();
for (int i = 0; i < 10000; ++i)
{
for (int j = 0; j < 5000; ++j)
{
list.Add(rnd.Next());
}
list.Sort((a, b) => a.CompareTo(b)); // #1
list.RemoveRange(0, 5000);
}
Console.WriteLine(sw.ElapsedMilliseconds);
Console.ReadLine();
}
基线性能:10047毫秒.
优化1:删除方法调用和分支
方法调用成本时间.分支也是如此.所以,如果我们不需要分支,我们也可以消除它.换句话说:这是关于(5).
想到的一件事是将#1替换为:
list.Sort((a, b) => a - b);
在大多数(!)场景中,这给出了期望的结果,我直截了当地假设这种情况也不例外.
测量:8768毫秒.(是的,这是15%的变化!)
为了它的乐趣,我们还对(2)做了一个简单的测试:
list.Sort((a, b) => (int)((float)a - (float)b));
它与运算符的大小完全相同(32位),它是完全相同的数据并且会给出相同的结果 - 我们只是将所有内容与不同的CPU操作进行比较并添加一些强制转换.测量:10902毫秒.如果每个操作只是一个时钟滴答,这比你预期的要多.
优化2:数组还是列表？
我也可以关心这个清单本身; 我们正在使用它进行相当多的调用,因此我们可能会将其替换为数组.RemoveRange如果我们反转排序顺序,我们甚至可以消除.那么我为什么不专注于那个呢？嗯,实际上我可以,但我可以告诉你它不会产生很大的不同,因为相对而言,它并不经常被称为.不过,测试没有坏处,对吧？:
static void Main(string[] args)
{
Random rnd = new Random(12839);
int[] list = new int[10000];
for (int i = 0; i < 5000; ++i)
{
list[i] = rnd.Next();
}
Stopwatch sw = Stopwatch.StartNew();
for (int i = 0; i < 10000; ++i)
{
for (int j = 0; j < 5000; ++j)
{
list[j + 5000] = rnd.Next();
}
Array.Sort(list, (a, b) => b - a);
}
Console.WriteLine(sw.ElapsedMilliseconds);
Console.ReadLine();
}
现在,这里有两个测量:
这并没有真正有所作为的原因是a的底层数据结构List是一个数组,所以如果我们正在排序,我们只是在做同样的事情.这就是我们的时间.
这里要记住的不是数组和a一样快List.事实是:我发现如果他们在很多情况下实际上更快.但是,在这种情况下,我们不是在谈论内部循环中的优化,我们不会过多地分配太多内存(可能一切都保存在缓存中)并且所有内存访问都是对齐的.总而言之,我们可以预期差异非常小.
优化3:删除更多方法调用
现在,您应该注意到这里还有一个替代方法:方法调用成本时间,这里调用最多的是比较器.因此,让我们回到解决方案,List并删除比较操作.当我们这样做时,我们仍然需要复制.你能指望什么？
将行更改为:
list.Sort();
......我们有一个新的时间:4123毫秒.
现在,为了完全公平,实际上我们在这里所做的是将内联委托更改为Comparer<int>.Default,这是整数比较器的默认实现.代表将被包装在比较器中,创建2个虚拟调用 - 这只是1个调用.这意味着我们可以通过实现我们自己的比较器类来颠倒顺序,这本来是一个更快的解决方案.
优化4:合并连接
如果我们只需要对一半的数据进行排序,为什么还要排序？这没有意义,对吧？
我再次选择最简单的算法来完成任务.我们按顺序遍历列表,并按顺序存储新项目,cf(1)和(3).没有交换,请记住我们更喜欢顺序数据访问模式.然后,我们只需删除所有不再需要的东西.
我们需要的算法是合并连接,其工作方式如下:
Stopwatch sw = Stopwatch.StartNew();
for (int i = 0; i < 10000; ++i)
{
for (int j = 0; j < 5000; ++j)
{
list.Add(rnd.Next());
}
// Sort the second half:
list.Sort(5000, 5000, Comparer<int>.Default);
// Both the lower and upper half are sorted. Merge-join:
int lhs = 0;
int rhs = 5000;
while (list.Count < 15000)
{
int l = list[lhs];
int r = list[rhs];
if (l < r)
{
list.Add(l);
++lhs;
}
else if (l > r)
{
list.Add(r);
++rhs;
}
else
{
while (list.Count < 15000 && list[lhs] == l)
{
list.Add(l);
++lhs;
}
while (list.Count < 15000 && list[rhs] == r)
{
list.Add(r);
++rhs;
}
}
}
list.RemoveRange(0, 10000);
}
我们有一个新的测量,它是3563毫秒.
优化5:RemoveRange#2
请记住,在突发中处理数据非常快.最后一段代码是展示这一点的绝佳机会.我们在RemoveRange这里使用一个处理突发数据的数据.我们也可以使用两个缓冲区并交换它们.基本上我们在list2合并连接期间写一秒钟并用以下内容RemoveRange替换:
list.Clear();
var tmp = list;
list = list2;
list2 = tmp;
我们现在有一个新的时间:3542毫秒.完全相同的!
从最后两个开始,你应该得出结论,做突发操作花费的时间很少,你通常不应该打扰.
结论
我已经开始使用一棵树,它在86220毫秒内执行了所有操作,最终得到了一个耗时3542毫秒的算法.相当直率这意味着最后一次实现在第一次尝试的4%时间内执行.
现在,我在这个长期答案中确实使用了不同的算法 - 但重点是向您展示如何进行所有这些优化以及优化的实际效果.