性能: SortedDictionary对SortedSet

Question

我要不要

1.)SortedDictionary(双，结构)

2.)或者仅仅是一个普通字典(double，struct)加上一个SortedSet(double)？

我只想要快速插入。我不关心检索，因为我不会做太多的查找。我需要排序自然，因为，我做的唯一的查找将是在最大双倍或几个最大双倍。

我觉得时间性能方面-两者是一样的，SortedSet<double>只是做额外的工作。你们能确认一下吗？

我不知道的部分是是否要维护排序，SortedDictionary只在键(双)或键和值之间移动。(后一种情况是第二种情况。)将超过1)，不是吗？

另外，还不清楚SortedDictionary是如何在内部实现的。Sortedset是一棵红-黑的树，是一个被证实的表演者.

Answer 1

SortedDictionary<K, V>是该走的路。不仅仅是因为它是适合你使用的结构，而且即使是从性能和维护的角度来看，它也会更好。

我只想要快速插入

1. 在第二种情况下，您必须同时插入Dictionary<K, V>和SortedSet<K>。这是两个插入(一个O(1)和其他O(log ))。我希望它比SortedDictionary<K, V> (O(log ))的单个插入要慢。
2. SortedDictionary<K, V>在内部实现为SortedSet<KeyValuePair<K, V>>，并在KeyValuePair<K, V>的Key部分上进行比较。因此，如果您对SortedSet<T>的性能感到满意，那么就不应该回头看。

排序字典只在键(双)或键和值之间移动。

，这显然是微观优化，，这只是一个移动几个额外字节的问题，这并不重要。

还不清楚排序字典是如何在内部实现的。这是一棵红-黑的树，是一个被证实的表演者.

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

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

警报：，我写上面的文章时还没看过你的评论!！

我使用的结构有点重~100字节。

如果你能把它改到课堂上，那就去做。如果你的应用是性能关键的话，移动大约100个字节就不太好了。

我制作了一个快速而肮脏的Dictionary<K, V>/SortedSet<K>混合结构，并对其进行了测试。

• 实际上，对于一个100字节的结构来说，插入速度更快(速度是插入速度的两倍多)。当然会有惩罚(谁会创建一个100字节的结构？)。
• 当我把它改为类时，它们的插入性能都是一样的。
• 当我缩小结构的大小时，即使这样，插入性能也是相当的。

因此，我的建议是切换到一个类并使用SortedDictionary<K, V>。如果您被结构卡住了，那么Dictionary<K, V>/SortedSet<K>会更好。q值好，+1。