C# (托管代码) 中的大型集合 - 第 II 部分

引言

设想您正在一家处理大数据集合的公司工作，并且您必须找到一种最佳的数据结构来处理数十亿条记录。我们如何知道哪种数据结构是最佳的，这是一个挑战，我在本次基准测试中试图解答这个问题。在开始阅读之前，请考虑以下几点：

1. 操作系统不是实时操作系统，因此我将呈现平均结果。
2. 二分查找 (BS) 需要排序，而此排序时间复杂度已从我的研究中放宽，因为您可以使用任何方便的排序算法，并将您的排序算法的复杂度加在我的结果之上。有关排序时间复杂度的更多信息，请参阅此链接。

什么是好的解决方案？

好的解决方案是能以最低的时间成本提供最大速度和容量的解决方案。显然，由于我工作的操作系统不是实时操作系统，因此我排除了确定性问题！但如果我们能找到一个更确定的解决方案，那就太棒了。

机器规格

将执行所有单元测试的机器具有以下硬件和软件配置：

• CPU: Intel (R) Core (TM) i7-6650U @ 2.2GHz (4 CPUs)，约 2.2GHz
• 内存：8 GB
• 操作系统: Windows 10 Pro
• Visual Studio 2017

背景

在本文中，我将从容量、速度和时间成本的角度，对使用 C# .NET 语言处理大数据集合进行一些性能基准测试。我选择的集合是 Array、List 和 Dictionary。

托管代码一词由微软提出，指的是在 CLR（如 .NET 或 Mono）的托管下执行的代码。有关托管代码和非托管代码的更多信息，请关注以下链接：

• MSDN 托管/非托管代码互操作概述
• 维基百科：托管代码

托管代码的执行可能不是非常确定的，因为 CLR 会干扰，因此，一个提供粗略估计的基准测试可能会非常有帮助。但是，在考虑此基准测试结果之前，我们最好回答以下两个问题：

1. 您的海量数据集集合的最大大小是多少？
2. 数据类型是什么？您将处理哪种类型的数据？整数、文本等。

正如您从结果中将看到的，每个集合的性能高度依赖于集合的大小以及在集合上使用的算法，例如搜索。

注意 1：请牢记，所有测试环境都运行在非实时操作系统上。这意味着结果不是确定的。为了克服这种不确定的结果，我已经执行了所有测试 100 次，因此您看到的是 100 次迭代的平均时间。

我考虑的操作是创建和搜索，因为这两者是最耗时和最重要的操作。

搜索操作

以下方法展示了搜索测试的模式。正如您从代码中看到的，我总是考虑最坏的情况，这意味着我要查找的项几乎位于集合的末尾。搜索算法被 Monitor 对象包围，该对象包含一个时钟，在进入搜索主体之前开始，并在找到集合中的项后立即停止。

[TestMethod]
[TestCategory("Owner [C'#' Array]")]
public void FindByForInArry()
{
    try
    {
        string find = mocklbl + (capacity - 1);
        Monitor.Reset();

        for (int j = 0; j < iteration; j++)
        {
            string found = "";
            Monitor.Start();
            for (int i = 0; i < capacity; i++)
            {
                if (array[i] == find)
                {
                    found = array[i];
                    break;
                }
            }
            Monitor.Stop();
            Assert.AreEqual(find, found);
        }

        Monitor.LogAvgElapsed("FindByForInArray");
    }
    catch (Exception ex)
    {
        Monitor.WriteLog(ex.Message);
        throw ex;
    }
}

搜索时间复杂度

从上图中有几个有趣的发现，我想列出如下：

1. 二分查找（上表中的第二列）在查找项时始终花费 0 毫秒。
2. 在所有搜索算法中，100 万条记录和 1000 万条记录之间的时间差异呈指数级增长（比较绿色线和黄色线）。
3. 字典数据结构无法处理 1000 万条记录（这就是为什么绿线不超出 FindbyFindInArray 的原因）。
4. 枚举查找是最差的搜索算法（见第三列）。
5. 在列表和数组上，搜索算法的顺序（从最好到最差）是：二分查找、Find、For 循环和枚举器对象。
6. 在 10 万条记录以上，数据结构和搜索算法之间没有显著差异。
7. 如果不需要键值对，那么带有二分查找的列表是最佳选择。

下一张图将展示相同集合（数组、列表和字典）的创建和写入时间复杂度。以下代码代表了这些测试的一个示例模式：

[TestMethod] 
[TestCategory("Owner [C'#' Array]")]
public void FetchMockData(long capacity = 1000)
{
    try
    {
        capacity = Monitor.BySize;
        for (int j = 0; j < 100; j++)
        {
            Monitor.Reset();
            Monitor.Start();
            array = new string[capacity];
            for (int i = 0; i < capacity; i++)
            {
                array[i] = mocklbl + i;
            }
            Monitor.Stop();

        }
        Monitor.WriteLog($"The creation of array took:{Monitor.AvgElapsedInMiliseconds}");

    }
    catch (Exception ex)
    {
        Monitor.WriteLog(ex.Message);
        throw ex;
    }
}

创建时间复杂度

以下是来自上一图的发现：

1. 在创建时间中也出现了 100 万条记录和 1000 万条记录之间相同的指数级复杂度。
2. 列表数据结构几乎超越了数组，并在达到 100 万条记录大小时击败了数组。
3. 字典的时间复杂度最差，仅在必要时才应使用。

结论

令人惊讶的是，List 数据结构表现如此之好，性能更优，并且与二分查找结合使用可以提供非常显著的性能优化。