.net - 性能:SortedDictionary 与 SortedSet

Question

我应该保持
1.) SortedDictionary(double,struct)
2.) 或者只是一个普通的 Dictionary(double,struct) 加上一个 SortedSet(double)？

我只想快速插入。我不关心检索，因为我不会做太多查找。我需要排序的性质，因为我所做的唯一查找将是最大 double 数或几个最大 double 数。

我觉得时间表现明智 -
两者都是一样的，SortedSet<double>只是做额外的工作。大家能确认一下吗？

我不知道的部分是是否保持排序，SortedDictionary只移动键( double )，或键和值。在后一种情况下，2.) 会胜过 1.)，不是吗？

另外，不清楚如何SortedDictionary是内部实现的。 Sortedset是经过验证的执行者的红黑树。

Answer 1

SortedDictionary<K, V>是要走的路。不仅因为它是适合您使用的正确结构，而且即使在性能和维护方面它也会更好。

I just want fast insertions

在第二种情况下，您必须将两者都插入 Dictionary<K, V>以及 SortedSet<K> .这是两次插入(一次 O(1) 和另一次 O(log n))。我希望它比对 SortedDictionary<K, V> 的单次插入慢(O(log n))。

SortedDictionary<K, V>在内部实现为 SortedSet<KeyValuePair<K, V>>在 Key 上进行比较KeyValuePair<K, V>的一部分.所以如果你对SortedSet<T>的表现满意的话，那就应该没有回头路了。

the sorteddictionary moves around just the keys (doubles), or both the keys and values

这显然是微观优化。 这只是移动几个额外字节的问题，这无关紧要。

its not clear how sorteddictionary is internally implemented. Sortedset is red-black tree which is a proven performer.

SortedDictionary<K, V>在内部实现为 SortedSet<KeyValuePair<K, V>>在 Key 上进行比较 KeyValuePair<K, V>的一部分. It is a red-black tree .所以这也是公认的表演者......

另请注意 SortedDictionary<K, V>内存会更轻，并且会导致更快的删除和枚举。 Dictionary<K, V>/ SortedSet<K>混合方法将为您提供更快的查找，但它必须在枚举期间为字典中的每个键查找相应的值部分。这会更慢。

警报:当我写上面的时候，我还没有阅读你的评论!!

the struct I am using is kinda heavy ~100 bytes

如果您可以将其更改为类，请执行此操作。如果您的应用程序对性能至关重要，则移动 100 字节左右不会很好。

我做了一个又快又脏的 Dictionary<K, V>/ SortedSet<K>混合结构并对其进行了测试。

实际上，在插入时 100 字节的结构更快(快两倍以上)。肯定会有惩罚(谁会创建一个 100 字节的结构？)。

当我将其更改为 class 时，它们都提供了相同的插入性能。

当我缩小结构体的大小时，即使如此，插入性能也相当。

所以我的建议是切换到一个类并使用 SortedDictionary<K, V> .如果您坚持使用结构，那么 Dictionary<K, V>/ SortedSet<K>会更好。好q，+1。