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

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

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

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

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

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

编辑

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

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

参考方案

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

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

一般在C#中的性能

大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,因此我们知道我们只是在处理具有预期特征的本机数据结构。

让我们从树形结构开始

另一个简单的解决方案是使用一棵红黑树。在.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);

在大多数(!)方案中,这都可以提供理想的结果,我直率地认为此方案也不例外。

测量: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毫秒-并没有太大区别
颠倒顺序将结果更改为7456 ms。

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

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

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

现在,您应该注意到这里还有一个替代方法:方法调用成本时间,而这里被称为“最耗时”的是比较器。因此,让我们使用List返回解决方案并删除比较操作。当我们这样做时,我们仍然必须复制。你能指望什么?

将行更改为此:

list.Sort();

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

现在,说句公道话,实际上我们在这里所做的就是将内联委托更改为Comparer<int>.Default,这是整数比较器的默认实现。该委托将被包装在比较器中,创建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毫秒内执行所有操作,最后以3542毫秒的算法结束。直截了当,这意味着最后的实现将在第一次尝试的时间中执行4%。

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

C#等效于Java List <?扩展类> - c#

我有泛型类的基本结构public class Parent<T> where T : Parent<T> { Action<T> Notify; } public class Child : Parent<Child> { } 我想要一个列表,以便可以将Child对象放在此处List<Parent>…

Java中的“ <<”运算符 - java

最喜欢的语句来自Java的Character类:(1 << Character.PARAGRAPH_SEPARATOR)) >> type PARAGRAPH_SEPARATOR是字节,type是整数。这句话中的操作员,他们做什么?如何以及在哪里可以使用这些运算符?这是oracles java.lang.Character文档。该类中…

在PHP中使用long int - php

我正在尝试此方法,但无法存储较大的价值$var = rand(100000000000000,999999999999999); echo $var; // prints a 9 digit value(largest possible) 如何获得期望值? 参考方案 PHP整数通常为32位。其他软件包提供了更高精度的整数:http://php.net/man…

List <Dog>是List <Animal>的子类吗?为什么Java泛型不是隐式多态的? - java

我对Java泛型如何处理继承/多态感到困惑。假设以下层次结构-动物(父母)狗-猫(儿童)因此,假设我有一个方法doSomething(List<Animal> animals)。根据继承和多态性的所有规则,我假设List<Dog>是List<Animal>,而List<Cat>是List<Animal&g…

将对象转换为List <object> - c#

我看过类似的问题,但没有什么合适的。我有一个碰巧包含列表的对象。我想把它变成我可以列举的东西。例如:object listObject; // contains a List<Something> List<object> list; list = listObject as List<object>; // list c…