优化Dictionary.TryGetValue()

Question

我正在编写一个计算成本很高的应用程序(NLP机器学习任务)，它需要优化。

因为我的代码有很多for循环，所以我使用了Parallel.For (和变体)来并行化最外层的循环。我还使用数组和Dictionary构建了一些索引，这大大降低了成本。

VS2010的分析器指出，应用程序的大部分时间都花在Dictionary.TryGetValue()上(这是索引的副产品)。

这就引出了一个问题:我是否能做得更好？又是如何做到的？

我的第一个问题是，是否有一个普遍的共识，即在我的场景中，ConcurrentDictionary.TryGetValue的表现比Dictionary.TryGetValue更好--很多读者，没有作者？

我没有动力编写我自己的hashmap，因为它的表现可能比.NET的集合更糟糕。但是，有没有库可以保证我的场景可以更快地进行查找呢？

也许hashcode的实现让事情变慢了？

Answer 1

根据MSDN的说法，Dictionary.TryGetValue已经得到了很好的优化：

此方法接近O(1)运算。

您还没有提到您的字典的键是什么，如果您使用自定义类型，请确保正确地实现了它的GetHashCode方法，因为字典和哈希表依赖于它并广泛使用它。

Answer 2

我的第一个问题是，是否有一个普遍的共识，即在我的场景中，ConcurrentDictionary.TryGetValue的表现比Dictionary.TryGetValue更好--有很多读者，没有作者？

我还没有测试过它，但我通常会期望并发实现会有额外的开销，总体上会稍微慢一些。不同之处在于你需要同步访问--也就是说，如果你的以读为中心的代码需要lock字典，那么并发版本(没有锁)可能会更快。既然您提到您的代码没有编写器，我猜您没有使用lock，因此没有任何理由将一个实现放在另一个实现之上。也就是说，它可能是值得分析的，但即使它更快(再说一次:我预计它会稍微慢一点)，我也只期望它稍微快一点-所以不太可能显着改变性能。

Answer 3

当查看profiler结果时，它声称一个方法在大部分执行时间内都是负责的，同样重要的是要弄清楚是不是因为：

1. 该方法已被调用太多次，或者
2. 单次调用该方法需要很长时间

如果TryGetValue因为被调用太多次而占用了大部分时间，这可能表明您需要降低索引/查找算法的复杂度，以便可以减少调用TryGetValue的频率。

只有在每次调用TryGetValue都需要很长时间的情况下，才值得进一步研究方法。然而，正如Pavel提到的那样，TryGetValue 本身的已经得到了很好的优化。这很可能是由TryGetValue调用的方法，也就是可以被您覆盖的方法，应该受到指责。通常，您需要注意GetHashCode和Equals方法。当调用TryGetValue时，它们都会被调用。Equals可能会被多次调用。我的经验是，Equals方法通常有更好的机会出现问题，因为某些框架构造的内置相等比较涉及到反思。