C#数组或List(T)哪个性能更好？

Question

有人能就这种情况给些建议吗： 我有100-500个元素，它们是动态的，也就是说每次请求时它们的数量总是不同的，包含元素名称、类型和ID。目前我正在使用多维数组。

public static Object[,] Item_data = new Object[500, 3];

然后我将数据设置到数组中：

int found_items = 0;
        foreach (Object m in queryCollection)
        {
            Item_data[found_items, 0] = m[0];

            Item_data[found_items, 1] = m[1];

            Item_data[found_items, 2] = m[0];
            found_plans++;
        }

我有8个同样结构的数组，其中填充了不同的数据，它们大约需要0.8-1.5秒的时间。问题是我需要按id、名称和类型对这些数组进行升序和降序排序。如果我手动使用另一个循环来排序数据，那么需要花费更多的时间。因此，我注意到List(T)具有排序功能，但根据这些主题，它要慢得多：Arrays vs. Lists的性能。

https://jacksondunstan.com/articles/3058

https://softwareengineering.stackexchange.com/questions/221892/should-i-use-a-list-or-an-array

在这种情况下使用List(T)值得吗？还是有其他推荐的东西？

- JonZ

---

你有进行基准测试吗？此外相关阅读：https://ericlippert.com/2012/12/17/performance-rant/ - UnholySheep

是否适合您的解决方案高度取决于您的数据和周围环境。因此，依赖处理一般性能方面的其他主题并不一定意味着在您的特殊情况下有意义。至少第三个链接向您展示了真正取决于您的用例使用哪种数据结构。除此之外，通常甚至不必考虑这一点，因为实际性能瓶颈通常在其他地方。 - MakePeaceGreatAgain

首先，对于可能具有原始类型（如int）的数据使用Object会导致访问效率非常低下。而且多维数组会导致访问不便。首先从语言中明显的部分开始（即具有属性的类，您可以使用内置的.OrderBy进行排序）。只有当这还不够快时，您才应该考虑一些花哨的东西，比如使用在线排序算法或B树在数据进入时对其进行排序，而不是之后再进行排序。此外，永远不要忘记数据库的存在，很多聪明的人已经对它们进行了优化。 - Jeroen Mostert

你在使用哪种排序代码来实现高速数组？ - MineR

@MineR 我不知道，这就是为什么我在这里尝试阅读社区建议以更好地完成它的原因。 - JonZ

Answer 1

如果你需要快速访问结构体，你尝试使用过 Dictionary<> 吗？你可以使用 System.Linq 进行排序。

https://msdn.microsoft.com/en-us/library/xfhwa508%28v=vs.110%29.aspx

- Bukk94

---

它在插入新值、删除特定索引 ID 的值以及使用字符串、整数、双精度等类型时速度是否相同？ - JonZ

它们在添加新项时具有相同的复杂度。但是，字典在删除或查找项目时具有更好的性能（因为它们使用键）。如果您有唯一的ID，则可以将其用作键。然后，查找或删除特定项将更快。 - Bukk94

字典和列表在速度上有什么区别？似乎字典的准备更简单。 - JonZ

我没有实际的基准测试数据，但是List大多数情况下是O(n)，而Dictionary大多数情况下是O(1)复杂度（我们谈论的是秒与毫秒之间的差别）。 - Bukk94

好的，我想我已经得到了我需要的一切。谢谢。主题已标记为答案。我本可以给予声望加分，但声望太低了。 - JonZ

Answer 2

List<T>在内部实现上使用T[]，只是它更灵活，在容量超过时会自动扩展。由于对于所有重要操作，它都在内部执行数组操作，只是提供了动态扩展的便利。

根据您的问题：

我有100-500个（它们是动态的，意味着每次请求它们的数量总是不同的）

现在理想情况下，new List<T>(100 / 200)是更好和最优选择，因为它会动态扩展以包含更多数据，但请注意，没有多维列表的概念，就像多维数组一样。虽然您可以使用类似于T[][]的东西来使用List<List<T>>创建类似于嵌套数组的结构，但是没有用List<T>替换T[,]的方法。多维数组适用于具有定义的下限和上限的矩阵形式数据。

这与内存优化有关，涉及到各种操作时，List<T>暴露了数组操作（原地排序），List<T>和T[]也暴露了IEnumerable<T>的Linq扩展API，但由于额外的内存分配以及它们是在通用接口上完成而不是特定数据结构上完成，因此它们不如原地排序高效。

现在考虑各种用例：

• 如果全部都是枚举/顺序数据处理，则T[]和List<T>都是高效的，事实上它们提供了二进制搜索选项，使得对于已排序的数据搜索为O(LogN)，比O(N)好得多，实际上您可以考虑使用默认排序的SortedList<TK,TV>，但只是它在内部是IDictionary，类似的还有SortedDictionary<TK,TV>，对于非常快速的元素搜索，没有任何替代品可以取代IDictionary<TK,TV>，它是O(1)。

所有上述观点都仅仅是理论，找到适合的内存和性能组合的最佳方式是通过使用各种数据结构测试您的用例，这样您就能够在最小程度上妥协地为所有用例找到合适的匹配。

- Mrinal Kamboj

---

微软表明列表可以创建对象，这样我就可以将多维数组扔进垃圾桶并使用List。https://msdn.microsoft.com/zh-cn/library/6sh2ey19(v=vs.110).aspx - JonZ

就像我之前提到的，你需要有一个非多维数组的使用案例才能让 List<T> 生效，更重要的是尝试使用各种使用案例来比较流行的数据结构，如 Dictionary<TK, TV>。 - Mrinal Kamboj