Dictionary, SortedDictionary, SortedList 比较

时间：2010-11-23 来源：shengtianlong

Dim TestObject As New SortedDictionary(Integer, Integer)
With TestObject
.Add(7,2)
.Add(0,1)
.Add(5,3)
.Add(1,1)
.Add(4,4)
End With
For Each kvp As Collections.Generic.KeyValuePair(Of Integer, Integer) In TestObject
MsgBox kvp.Key
Next

复制代码

得到的顺序是 0, 1, 4, 5, 7 (SortedList 同样)
但是如果把 SortedDictionary 换成 Dictionary, 结果就是 7, 0, 5, 1, 4.

另一种遍历方法:

With TestObjectx.GetEnumerator()
While .MoveNext()
MsgBox(.Current.Key)
End While
End With

复制代码

--- 华丽的分割线 ---

SortedList<(Of <(TKey, TValue>)>) 泛型类是具有 O(log n) 检索的二进制搜索树，其中 n 是字典中元素的数目。就这一点而言，它与 SortedDictionary<(Of <(TKey, TValue>)>) 泛型类相似。这两个类具有相似的对象模型，并且都具有 O(log n) 的检索运算复杂度。这两个类的区别在于内存的使用以及插入和移除元素的速度：

SortedList<(Of <(TKey, TValue>)>) 使用的内存比 SortedDictionary<(Of <(TKey, TValue>)>) 少。

SortedDictionary<(Of <(TKey, TValue>)>) 可对未排序的数据执行更快的插入和移除操作，它的运算复杂度为 O(log n)，而 SortedList<(Of <(TKey, TValue>)>) 的运算复杂度为 O(n)。

如果使用排序数据一次性填充列表，则 SortedList<(Of <(TKey, TValue>)>) 比 SortedDictionary<(Of <(TKey, TValue>)>) 快。

SortedDictionary<(Of <(TKey, TValue>)>) 类和 SortedList<(Of <(TKey, TValue>)>) 类之间的另一个区别是：SortedList<(Of <(TKey, TValue>)>) 支持通过由 Keys 和 Values 属性返回的集合对键和值执行高效的索引检索。访问此属性时无需重新生成列表，因为列表只是键和值的内部数组的包装。

二叉树的插入操作怎么是 O(n)?

网上有一种说法, 就是 SortedList 内部就是两个数组, 插入的时候类似 O(n^2) 的插入排序 (每个动作为 O(n)), 不过插入有序数据特别快 (每个动作变成 O(1)). 同样的情况出现在删除数据.

Dim TestObject As New SortedList(Of Integer, Integer)
For i As Integer = 1 To 1000000
TestObject.Add(i, RandomGenerator.Next())
Next

复制代码

当然, RandomGenerator 是我们的随机数发生器:

Dim RandomGenerator As New Random

复制代码

上述代码执行速度相当快, 因为插入的数据的 Key 值是有序的.
如果把 i 换成 1000000 - i, 则速度立刻慢得惨不忍睹.
同样的情况出现在把 i 替换成随机数. 在一段时间的等待后出错: 因为 Key 值不能重复.
这样说来, SortedList 不太像二叉树结构.

SortedList 还有一个功能, 就是直接访问 Key 值大小排名为 k 的 Key 和 Value.
方法是 Object.Keys(k) 和 Object.Values(k).
这更加印证了网上的说法.

我认为 SortedList 没什么用 - 除非是对基本有序的数据, 或者对内存非常吝啬. 如果仅仅需要在 BST 上加上查找排名为 k 的节点的功能, 可以使用一个经典算法: 在每个节点上加上一个 leftsize, 储存它左子树的大小. (当然也可以用 CQF 的 SBT. 那个 SB maintain... 扯远了~)

2. 功能
这三个类的功能上面都讲得差不多了. 因为实现就决定了功能. 这里小结一下.
Dictionary 的功能:
Add<K,V>, Clear, Contains<K/V>, GetCount, Enumerator (无序), GetItem<K>, Remove<K>
SortedDictionary 新增的功能:
Enumerator 为有序 - 对应 BST 的中序遍历.
SortedList 新增的功能:
Capacity(Set/Get) - 毕竟人家是数组
IndexOfKey, IndexOfValue (返回 Value 对应 Key 的排名而不是 Value 的排名)
Keys(k), Values(k) - 返回按照 Key 排序的数组的第 k 个元素

3. 速度
实践出真知 - 某名人.
理论和实践不符就是错的 - Thity.

我们的测试程序:

Module DictionarySpeedTest
Dim RandomGenerator As New Random
Dim ArrayListData As New List(Of Key_N_Data)
Dim TestObject As New Dictionary(Of Long, Long)
Structure Key_N_Data
Dim Key As Int64
Dim Data As Int64
End Structure
Const ITEM_COUNT As Integer = 1000000
Const TEST_COUNT As Integer = 500000
Dim LastTick As Long
Sub TimerStart(ByVal Text As String)
Console.Write(Text)
LastTick = Now.Ticks
End Sub
Sub TimerEnd()
Dim t As Integer = Now.Ticks - LastTick
Console.WriteLine(((t) \ 10000).ToString() & " ms")
End Sub
Sub Main()
Process.GetCurrentProcess.PriorityClass = ProcessPriorityClass.High
Console.WriteLine(TestObject.GetType().ToString())
TimerStart("Generating data... ")
For i As Integer = 1 To ITEM_COUNT
Dim ThisKeyData As Key_N_Data
ThisKeyData.Key = (CLng(RandomGenerator.Next()) << 31) or RandomGenerator.Next()
ThisKeyData.Data = (CLng(RandomGenerator.Next()) << 31) or RandomGenerator.Next()
ArrayListData.Add(ThisKeyData)
Next
TimerEnd()
TimerStart("Test 1: add data test... ")
For Each Item As Key_N_Data In ArrayListData
TestObject.Add(Item.Key, Item.Data)
Next
TimerEnd()
TimerStart("Test 2: find data test... ")
For i As Integer = 1 To TEST_COUNT
With ArrayListData.Item(RandomGenerator.Next(0, ITEM_COUNT))
If Not Equals(TestObject(.Key), .Data) Then MsgBox("Error!")
End With
Next
TimerEnd()
TimerStart("Test 3: remove data test...")
For i As Integer = 1 To TEST_COUNT
TestObject.Remove(ArrayListData.Item(RandomGenerator.Next(0, ITEM_COUNT)).Key)
Next
TimerEnd()
End Sub
End Module

复制代码

通过更改 TestObject 的类型, 我们可以很方便地比较这三个类的速度. 测试结果:

               ADD FIND REMOVE
Dictionary    265ms  203ms  187ms
SortedDictionary 1843ms 828ms  1234ms
SortedList    N/A

我们把 ITEM_COUNT 和 TEST_COUNT 都减小 10 倍:

               ADD FIND REMOVE
Dictionary    15ms 31ms 15ms
SortedDictionary 93ms 46ms 38ms
SortedList    8031ms 15ms 6046ms

SortedList 的随机查找居然比 Dictionary 和 SortedDictionary (Hashtable 和 BST) 还要快. 这样说来, SortedList 似乎又不是简单的数组了. (不过我仍然觉得它没什么用)

4. 小结
如果只是当作索引使用, 请用 Dictionary.
如果需要查找最小的几个元素, 或者需要按顺序遍历元素, 就用 SortedDictionary.
如果输入/删除的元素是基本增序的, 或者访问次数远多于修改次数, 或者需要访问第 k 大的元素, 或者对内存吝啬得 BT 的情况, 用 SortedList 吧. (它居然成使用情况最多的了... orz)

PS: 微软似乎也很吝啬, SortedDictionary 居然只支持增序 (默认的比较器), 如果要降序的话, 我们得自己写一个比较器.

Class MyComparer
Inherits Comparer(Of Long)
Public Overrides Function Compare(ByVal x As Long, ByVal y As Long) As Integer
Return Comparer(Of Long).Default.Compare(y, x)
End Function
End Class
Dim TestObject As New SortedList(Of Long, Long)(New MyComparer)

复制代码

现在我们可以来进行一下刚开始的时候提到的 Dictionary vs Hashtable 对决.

Const ITEM_COUNT As Integer = 1000000
Const TEST_COUNT As Integer = 500000

复制代码

ADD FIND  REMOVE
Dictionary(Of Long, Long)    271ms 203ms 187ms
Dictionary(Of Object, Object) 468ms 312ms 234ms
Hashtable                   859ms 390ms 218ms

结论: 最好用 Dictionary 代替 Hashtable.