我应该担心.NET字典速度吗？

Question

我应该担心.NET字典速度吗？

c#arraysoptimizationdictionary

28

我将创建一个需要频繁使用字典查找和插入的项目。这个会不会成为一个问题？

如果我进行基准测试，结果很差，那么用什么替代字典是最好的方式？使用带有“哈希”键的数组是否更快呢？但这对于插入时间没有帮助，对吗？

此外，我认为我并没有微优化，因为这确实会是生产服务器上代码的一个重要部分，所以如果这需要额外100毫秒才能完成，那么我们将寻找新的处理方式。

- Earlz

4

如果字典存储和查找是算法的核心部分，那么需要进行基准测试。这实际上比在 Stack Overflow 上询问要花费更少的时间 :) - orip

字典真的很快。也可以查看这些问题：https://dev59.com/pXI95IYBdhLWcg3wyRI0https://dev59.com/ZFPTa4cB1Zd3GeqPil0y - nawfal

12个回答

69

你好，我将创建一个需要频繁使用字典查找和插入的项目。这个会有什么问题吗？

是的，始终要考虑性能因素。你应该关注以下几点：写出现实的、以用户为中心的性能规范；尽早编写性能测试，并经常运行它们，以便了解每个对产品的更改如何影响性能。这样，当代码更改导致性能发生影响时，你可以立即得到通知。此外，你应该经常进行性能分析，这样你就可以根据实际测量结果而不是随意猜测来思考性能。

如果我的基准测试结果差强人意，那么用别的东西替换字典的最佳方法是什么？

最好的方法是构建一个合理的抽象层。如果你有一个表示“插入”和“查找”抽象数据类型的类（或接口），那么你可以替换其内部而不改变任何调用者。

请注意，添加抽象层本身会带来性能成本。如果你的性能分析表明抽象层过于昂贵，如果每次调用额外的几个纳秒时间太多，那么你可能必须摆脱这个抽象层。同样，这个决策将受到真实世界性能数据的驱动。

使用带有“哈希”键的数组是否更快？但这对插入时间没有帮助，对吗？

在真实环境下，无论是你还是任何人都不可能知道哪一个方案更快，除非你同时编写并在真实情况下对其进行基准测试。在“实验室”条件下进行测试会导致结果偏差；你需要了解在GC受到现实内存压力时的工作原理等等。这就好比让我们预测明年肯塔基德比赛中哪匹马将跑得更快一样。如果我们仅凭比赛记录就能猜出答案，我们早已致富了。你不可能指望有人知道两个完全假设、未编写的代码片段在未指定条件下哪一个更快！

- Eric Lippert

1

我同意并实践了这种使用接口/抽象的方法，然后根据性能测试结果进行移除。而且我要补充一点，不要过早地移除该接口！这可能会导致未来设计灵活性的损失，从而需要进行大量重构...我也曾经历过这种情况。 - Paul

3

我猜2010年肯塔基德比赛中的“超级节省者”。 - LarsTech

10

Dictionary<TKey, TValue>类实际上是以哈希表的形式实现，使查找非常快速（接近O（1））。有关更多信息，请参见API文档。我怀疑你自己也无法做出更好的实现。

- Anders Fjeldstad

14

不要对此过于挑剔，但O(1)并不意味着它就很快，只是意味着它的时间复杂度是恒定的。但这个恒定时间可能很长或很短。尽管如此，在实践中，O(1)倾向于很快。 - JulianR

10

如果您的应用程序的性能低于预期，请先观察一段时间
如果确实如此，那么请使用分析器确定字典查找是否是问题的源头
如果确实是这样，请使用代表性数据进行测试，以查看选择另一个列表是否会更快。

总之 - 通常情况下，在出现问题之前不必担心实现细节的性能。

- Justin

5

我建议您对字典、哈希表（在.NET中为HashSet）以及可能的自定义类进行基准测试，看看在您的典型使用条件下哪个效果最好。

通常情况下，我会说这没问题（插入StackOverflow最喜欢的“过早乐观”的名言），但如果这是应用程序的核心部分，请务必进行基准测试。

- Neil N

3

一个 Dictionary<TKey, TValue> 应该始终优于一个 HashTable。即使在存在 Dictionary<TKey, TValue> 之前，.NET 的 HashTable 也是个不好的想法 :) - Cory Charlton

1

应该是 HashSet<T>，我从来不喜欢 .Net 中旧的 HashTables。 - Neil N

4

我不确定是否有人已经回答了这部分内容：

此外，如果我进行基准测试等，并且结果非常糟糕，那么用其他东西替换字典的最佳方法是什么？

对于这个问题，尽可能将变量声明为IDictionary。那是Dictionary派生的主要接口。(我假设如果您非常关心性能，那么您不会考虑非泛型集合。)然后，在未来，您可以更改底层实现类，而无需更改使用该字典的任何代码。例如：

IDictionary<string, int> myDict = new Dictionary<string, int>();

- Travis

@Morbo：Eric Lippert在他的回答中说：“做到这一点的最好方法是构建一个合理的抽象层。” - John Saunders

4

我能想到的唯一问题是，字典速度依赖于键类具有相当快的 GetHashCode 方法。查找和插入非常快，所以你不应该在这方面遇到任何问题。

关于使用数组，在 Dictionary 类中已经使用了它。实际上，它使用两个数组，一个用于键，另一个用于值。

如果你在使用 Dictionary 时遇到任何性能问题，很容易制作一个包装器，它具有与 Dictionary 相同的方法和行为，这样你就可以无缝替换它。

- Guffa

2

如果您的应用程序是多线程的，那么性能的关键部分将是正确同步此字典。

如果它是单线程的，则几乎肯定瓶颈将在其他地方。例如从任何地方读取这些对象。

- yu_sha

2

我使用字典作为UDP中继服务器。每次数据包到达时，它会执行Dictionary.ContainsKey和Dictionary[Key]，效果非常好（有大量的客户端）。在制作过程中我曾经有些担心，但现在看来这是我最不应该担心的事情。

- Ivan

1

看一下C# HybridDictionary用法

HybridDictionary类

推荐在字典中元素数量未知的情况下使用此类。它利用了ListDictionary在小集合中的改进性能，并提供了灵活性，可以切换到Hashtable，在处理大集合时比ListDictionary更优秀。

- Adriaan Stander

1

非泛型等于非启动程序，对我来说。不过我确实想知道他们为什么从没有制作这个类的泛型版本。 - Joel Mueller

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Saunders · Accepted Answer

你正在进行微观优化。你是否已经有运行的代码？记住，“如果它不工作，那么它有多快也没关系。”(Mich Ravera) http://www.codingninja.co.uk/best-programmers-quotes/.

你不知道瓶颈在哪里，现在就专注于字典了。如果问题出在别的地方呢？
你怎么知道Dictionary类是如何实现的？也许它已经使用了带有哈希键的数组！

P.S. 真正的“ .NET Dictionaries” 而不是“ C# Dictionaries”，因为C#仅是使用该框架的几种编程语言之一。