性能:SortedDictionary与SortedSet

Question

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

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

我觉得时间表现明智 - 两者都是一样的,SortedSet<double>只做额外的工作.你们能证实吗？

我不知道的部分是维持排序,SortedDictionary仅仅是键(双打),还是键和值的移动.在后一种情况下2.)将胜过1.),不是吗？

此外,尚不清楚SortedDictionary内部如何实施.Sortedset是红黑树,是一个经过验证的表演者.

Answer 1

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

我只想要快速插入

1. 在第二种情况下,你将不得不既插入Dictionary<K, V>以及SortedSet<K>.这是两次插入(一次O(1)和另一次O(log n)).我希望它比单个插入SortedDictionary<K, V>(O(log n))慢.

2. SortedDictionary<K, V>是内部实现的SortedSet<KeyValuePair<K, V>>,比较是在Key部分KeyValuePair<K, V>.所以,如果你对表现感到满意SortedSet<T>,那就不应该回头了.

sorteddictionary只移动键(双精度),或键和值

这显然是微观优化.这只是移动几个额外字节的问题,这几乎不重要.

尚不清楚sorteddictionary如何在内部实施.Sortedset是红黑树,是经过验证的表演者.

SortedDictionary<K, V>是内部实现的SortedSet<KeyValuePair<K, V>>,比较是在Key部分KeyValuePair<K, V>. 这是一棵红黑树.所以这也是行之有效的......

另请注意,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.