原生和托管代码中的大型集合（VB、C++、C#）- 第一部分

以前

在开始阅读本文之前，请注意以下几点：

• 本文的第一部分主要目标是评估在不同数据结构上搜索不同类型数据的方法，而对不同语言的评估将在下一部分进行。 
• Windows 不是一个实时操作系统（RTOS），因此它的作业调度非常不确定。
• 微软已经发布了 .NET 源代码（C# 编写），这使得您可以阅读和理解复杂数据结构的实现方式，但由于 CLR 的架构，它仍然不是非常清晰。
• 我强烈建议，在开始阅读本文之前，先阅读有关通用语言运行时（CLR）和即时编译器（JIT）的内容。
• 结果未经平均或标准化，而是通过一次性执行收集的。
• 时间分辨率基于微秒。
• 尝试从 git 仓库检出源代码。我已经尝试展示一些技巧，例如在 VB 和 C# 中使用原生代码，设置 C++/CLI，以及使用单元测试来测试整个项目等等。

引言

假设您是一家从事大型数据集合业务的公司中的软件工程师，您必须拿出最好的平台、语言和数据结构，为公司的业务提供良好的竞争优势。

软件开发的最新趋势强调了大规模运行时数据处理，几乎所有应用程序都面临大规模数据处理的复杂性和开销。

在本文中，我将尝试为以下重要问题提供一个初步的答案：

• 对于将涉及整个系统的团队、产品和解决方案来说，哪种语言是最佳选择？
• 数据结构能否加速您的算法？

要回答上述问题，您需要对您的编程编译器和数据结构有一个正确的估计。

背景

作为一名程序员，我一直思考不同数据结构在不同算法执行时间和不同数据类型内容下的性能。我总是很难预测在程序生命周期中，已定义数据结构在不同事件和状态下的行为。

我相信面向对象编程引入了非常强大的概念来改进编程科学，但也增加了一些概念上的复杂性，甚至理解代码的难度。例如封装，它使得程序员对诸如 List、List<T>、Dictionary 等非原始数据结构的细节一无所知。（在此 处查找有关这些数据结构的更多详细信息）。

例如，几乎所有接触过 C#.NET、VB.NET 或 Java 等高级编程语言的人都知道不同类型的变量、数组、动态列表和字典。但也许只有少数程序员知道这些复杂数据结构的详细实现。虽然对每种数据结构的细节有扎实的了解会极大地影响执行时间，但程序员通常只信任框架，而不考虑任何由数据结构驱动的瓶颈。

也许其他人也和我一样，在 .NET Framework 支持的语言（如 C#、VB 或 C++）及其数据结构下进行编程。但就我个人而言，我从未考虑过使用的数据结构的细节，因为我对这个“黑匣子”存在错误的信任，它不清楚是如何工作的。本文的其余部分将更详细地解释这种错误信任的含义。

Using the Code

为了回答上述两个问题，我尝试通过一种简单的方法对 .NET Framework 下的大型数据结构进行初步的基准测试。这种方法非常简单，我只定义了两种不同的数据结构（Dictionary 和 List），分别具有 4 种基本大小：10,000、100,000、1,000,000 和 10,000,000。然后，我使用一个简单的函数来填充每个数据结构，就像下面的即时代码一样。

  private static void FetchMockData(int length)
        {
            if(list.Count > 0)
                length = Monitor.Length += Monitor.Length;
            for (int i = list.Count; i < length; i++)
            {
                list.Add(mocklbl + i);
            }
        }

之后，我使用以下方法来查找一个项。请注意，由于最坏情况场景，该项总是最后一个项。

• 在 Dictionary 中：
  • 按值查找 (GetValue)
  • 按键查找 (ByKey)
• 在 List 中：
  • Find 方法 (Find)
  • 二分查找 (BinarySearch)
  • For 循环查找 (For)
  • 枚举器查找 (Enumerator)

  [TestMethod]
        [TestCategory("Owner [C'#' Dictionary]")]
        public void FindByGetValueInDictionary()
        {

            string find = mocklbl + (dictionary.Count - 1);
            Monitor.Start();
            object found = dictionary.TryGetValue(find, out found);
            Assert.AreEqual(true, found);
            Monitor.Stop();
            WrappedMonitor.Elapsed("FindByGetValueInDictionary");
        }

     [TestMethod]
        [TestCategory("Owner [C'#' Dictionary]")]
        public void FindByKeyInDictionary()
        {

            string find = mocklbl + (dictionary.Count - 2);
            Monitor.Start();
            object found = dictionary[find];//Can raise an error
            Assert.AreEqual(find, found);
            Monitor.Stop();
            WrappedMonitor.Elapsed("FindByKeyInDictionary");
        }

       [TestMethod]
        [TestCategory("Owner [C'#' List]")]
        public void FindByFindInList()
        {
            string find = mocklbl + (list.Count - 1);
            Monitor.Start();
            string found = list.Find(i => i == find);
            Assert.AreEqual(find, found);
            Monitor.Stop();
            WrappedMonitor.Elapsed("FindByFindInList");
        }

        [TestMethod]
        [TestCategory("Owner [C'#' List]")]
        public void FindByBinarySearchInList()
        {
            string find = mocklbl + (list.Count - 1);
            Monitor.Start();
            int found = list.BinarySearch(find);
            Assert.AreEqual(list[found], find);
            Monitor.Stop();
            WrappedMonitor.Elapsed("FindByBinarySearchInList");
            Monitor.Reset();
            FetchMockData(Monitor.Length);
            FindByBinarySearchInList();
        }

        [TestMethod]
        [TestCategory("Owner [C'#' List]")]
        public void FindByForInList()
        {
            string find = mocklbl + (list.Count - 1);
            int length = list.Count;
            Monitor.Start();
            string found = "";
            for (int i = 0; i < length; i++)
            {
                if (list[i] == find)
                {
                    found = list[i];
                    break;
                }
            }
            Assert.AreEqual(find, found);
            Monitor.Stop();
            WrappedMonitor.Elapsed("FindByForInList");
            Monitor.Reset();
            FetchMockData(Monitor.Length);
            FindByForInList();
        }

        [TestMethod]
        [TestCategory("Owner [C'#' List]")]
        public void FindByEnumiratorInList()
        {
            string find = mocklbl + (list.Count - 1);
            Monitor.Start();
            IEnumerator iEunm = list.GetEnumerator();
            string found = "";
            while (iEunm.MoveNext())
            {
                if (iEunm.Current.Equals(find))
                {
                    found = (string)iEunm.Current;
                    break;
                }
            }
            Assert.AreEqual(find, found);
            Monitor.Stop();
            WrappedMonitor.Elapsed("FindByEnumiratorInList");
            Monitor.Reset();
            FetchMockData(Monitor.Length);
            FindByEnumiratorInList();
        }

请注意，此基准测试是在 Windows 操作系统下完成的，它不是一个确定性操作系统。这意味着如果我们运行上述任何代码，执行时间都会有所不同。但是，总体结果足以进行粗略估计。

供您参考，我将列出我的机器规格：

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

重要提示：所有实现的 C# 代码都已在 CLR 下编译，未启用任何优化标志，也未进行任何特定设置，结果也未进行平均或标准化。

关注点

在此，我想在没有任何调查或审查的情况下展示已完成的结果，因为我将继续撰写该系列文章的更多后续部分，并会详细讨论原因。请注意，时间分辨率以微秒为单位，在一轮执行周期后显示在 X 轴上。

请关注后续部分，并祈祷我能找到时间再次写作。

要访问文章的源代码，请使用此 链接，并请注意该项目尚在开发中，可能会有持续的更改。我还在尝试为这些结果添加更多语言和原生代码。

GitHub。

历史

• 2017 年 3 月 6 日：初版