C#最有效的数据结构，可插入和删除下半部分

Question

想象一下，我有一个很大的整数列表(> 1000个项目)。我需要能够对此列表执行两项操作:删除下半部分，然后通过插入随机整数再次将列表填充到其原始大小。因为我执行这些操作大约一百万次，所以我需要它尽可能地高效。

我做的第一件事就是使用List，通过在正确的位置添加新项来对其进行排序。尽管删除排序列表的下半部分非常容易，但是插入需要花费大量时间。

我尝试实现跳过列表，但是经过一些测试，列表的大小似乎至少必须为10000，才算真正重要，否则它的性能甚至比正常列表还要差。

这就是为什么我决定使用AVL树的原因，因此可以更快地插入项目。但是问题是我不知道删除这种二进制搜索树下半部分的任何有效方法。

我的问题是:是否有一种有效的方法来做到这一点？有没有我可以更轻松使用的另一种数据结构？

编辑

根据要求，我做了一个小测试，显示了列表，跳过列表和AVL树之间的性能差异。我在msdn:Skip list tutorial上使用本教程制作了跳过列表。 AVL树来自此处:AVL tree。我在Pastebin上上传了测试:Program。

在测试中，我在计时的同时向每个数据结构添加了100 000个项目。在我的电脑上，列表花费了大约1秒钟，跳过列表花费了0.5秒，AVL树花费了0.045秒。如果我愿意这样做一百万次，则该列表将花费大约11.5天，而AVL树仅需要大约半天。这种时差清楚地表明了我为什么要高效。

Answer 1

我想指出一些有关此问题的内容。首先，让我们直接了解一些有关性能和C#的知识，因为在仍然存在误解的同时，很难解释一些东西。

接下来，我将在这里将所有内容应用于特定问题。

一般在C#中的性能

Big-O表示法

在大学里，您将学习O(n)总是比O(n ^ 2)更好，以及O(n)总是比O(n log n)更好。但是，对此的基本假设是每个操作将花费大致相同的时间量。

现在，当我在1986年首次开始在1802 RISC处理器上进行编程时，情况就是这样:内存操作是1个时钟滴答，加，减等也是如此。换句话说，Big-O在这里可以正常工作。

在现代计算机中，这更加困难:

数据以各种级别缓存(速度范围从15 GB/s到1000 GB/s)；

操作在0.5个时钟滴答和数十个时钟滴答之间变化；

数据通常以突发方式获取-因此随机访问比顺序访问要差得多；

向量化可一次处理多达8个整数的对齐数据；

分支预测错误可能会使所有事情失去平衡，因为您必须冲洗很多。

我观察到，同一算法的不同实现的性能差异可能高达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，因此我们知道我们只是在处理具有预期特征的 native 数据结构。

让我们从树结构开始

另一个简单的解决方案是使用一棵红黑树。在.NET中我们可以使用一个称为 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，并且总是喜欢具有最简单数据结构(read:array)的算法。在这种情况下，它是一个与标准排序组合的列表，它将为每种排序提供 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);

在大多数(!)方案中，这都可以提供理想的结果，我直言不讳地认为该方案也不异常(exception)。

测量: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();
}

现在，这里有两个度量值:

将列表更改为数组只会将其更改为+/- 8700 ms-

并没有多大区别

颠倒顺序将结果更改为7456 ms。

之所以没有真正起什么作用，是因为 List的底层数据结构是一个数组，因此，如果我们进行排序，我们将在做同一件事。这就是我们的时间。

这里要记住的事情不是数组像 List一样快。事实是:我发现如果是这样，它们实际上在很多情况下会更快。但是，在这种情况下，我们不是在讨论内循环中的优化，也不是在分配过多的内存(所有内容都可能保留在缓存中)，并且所有内存访问都已对齐。总而言之，我们可以因此期望差异很小。

优化3:删除更多方法调用

现在，您应该注意到这里还有另一种选择:方法调用花费时间，而这里被称为最多的是比较器。因此，让我们回到带有 List的解决方案并删除比较操作。当我们这样做时，我们仍然必须复制。你能指望什么？

将行更改为此:

list.Sort();

...，我们有了一个新的计时:4123毫秒。

现在，为了公平起见，实际上，我们在这里所做的实际上是将内联委托(delegate)更改为 Comparer<int>.Default，这是整数比较器的默认实现。该委托(delegate)将被包装在比较器中，创建2个虚拟调用-这只是1个调用。这意味着我们也可以通过实现自己的比较器类来颠倒顺序，这将是一个更快的解决方案。

优化4:合并加入

如果只需要排序一半的数据，为什么还要排序所有内容？那是没有道理的，对吧？

同样，我选择了最简单的算法来简化任务。我们按顺序浏览列表，并按顺序存储新项目，请参见c.f。 (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，它以突发方式处理数据。我们还可以使用两个缓冲区并交换它们。基本上，我们在merge-join期间编写第二个 list2并将 RemoveRange替换为:

list.Clear();

var tmp = list;
list = list2;
list2 = tmp;

现在，我们有了一个新的计时:3542毫秒。一模一样!

从最后两个中，您应该得出结论，执行突发操作花费的时间很少，因此您通常甚至不必理会。

结论

我从一棵树开始，该树在86220 ms内执行了所有操作，最后以花了3542 ms的算法结束。直截了当，这意味着最后的实现将在第一次尝试的4％的时间内执行。

现在，在整个长答案中，我确实使用了不同的算法-但重点是向您展示如何进行所有这些优化以及优化实际上具有的效果。