[转帖]Dictionary, SortedDictionary, SortedList 横向评测

[转帖]Dictionary, SortedDictionary, SortedList 横向评测

原文地址: http://vip.366tian.net/iceboy/blog/article.asp?id=19

本文为 iceboy 原创. 转帖请注明出处.
做人要厚道.
Dictionary, SortedDictionary, SortedList 是 .NET Framework 的三个支持泛型和关键字查找的类, 都属于 System.Collections.Generic 命名空间. 它们无论是名字还是功能都十分相似, 以至于实际运用的时候我们会经常混淆. 因此有必要比较一下它们.

1. 实现
查阅 MSDN 得到如下资料:
Dictionary<(Of <(TKey, TValue>)>) 泛型类提供了从一组键到一组值的映射。字典中的每个添加项都由一个值及其相关联的键组成。通过键来检索值的速度是非常快的，接近于 O(1)，这是因为 Dictionary<(Of <(TKey, TValue>)>) 类是作为一个哈希表来实现的。
检索速度取决于为 TKey 指定的类型的哈希算法的质量。

可见, Dictionary 基本上就是一个 Hashtable. 不过它比 Hashtable 类快, 因为它支持泛型~ (稍后我们会用实验证明, 即使使用 Object 类型的 Dictionary 也比 Hashtable 稍快).

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

SortedDictionary<(Of <(TKey, TValue>)>) 泛型类是检索运算复杂度为 O(log n) 的二叉搜索树，其中 n 是字典中的元素数。就这一点而言，它与 SortedList<(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>)>) 快。

每个键/值对都可以作为 KeyValuePair<(Of <(TKey, TValue>)>) 结构进行检索，或作为 DictionaryEntry 通过非泛型 IDictionary 接口进行检索。

只要键用作 SortedDictionary<(Of <(TKey, TValue>)>) 中的键，它们就必须是不可变的。SortedDictionary<(Of <(TKey, TValue>)>) 中的每个键必须是唯一的。键不能为 nullNothingnullptrnull 引用（在 Visual Basic 中为 Nothing），但是如果值类型 TValue 为引用类型，该值则可以为空。

SortedDictionary<(Of <(TKey, TValue>)>) 需要比较器实现来执行键比较。可以使用一个接受 comparer 参数的构造函数来指定 IComparer<(Of <(T>)>) 泛型接口的实现；如果不指定实现，则使用默认的泛型比较器 Comparer<(Of <(T>)>)..::.Default。如果类型 TKey 实现 System..::.IComparable<(Of <(T>)>) 泛型接口，则默认比较器使用该实现。

C# 语言的 foreach 语句（在 C++ 中为 for each，在 Visual Basic 中为 For Each）需要集合中每个元素的类型。由于 SortedDictionary<(Of <(TKey, TValue>)>) 的每个元素都是一个键/值对，因此元素类型既不是键的类型，也不是值的类型。而是 KeyValuePair<(Of <(TKey, TValue>)>) 类型。

可见, SortedDictionary 类似一个平衡二叉查找树 (AVL). 既然是 BST, 我们当然可以对其进行中序遍历. 有两种方法:
1. For Each
2. Object.GetEnumerator

小实验:

CODE:

 1Dim TestObject As New SortedDictionary(Integer, Integer)
 2With TestObject
 3    .Add(7,2)
 4    .Add(0,1)
 5    .Add(5,3)
 6    .Add(1,1)
 7    .Add(4,4)
 8End With
 9
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.

另一种遍历方法:

CODE:
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 属性返回的集合对键和值执行高效的索引检索。访问此属性时无需重新生成列表，因为列表只是键和值的内部数组的包装。

QUOTE:

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

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

 

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

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

 CODE:
 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.

我们的测试程序:

 1CODE:
 2Module DictionarySpeedTestModule DictionarySpeedTest
 3    Dim RandomGenerator As New Random
 4    Dim ArrayListData As New List(Of Key_N_Data)
 5    Dim TestObject As New Dictionary(Of Long, Long)
 6
 7    Structure Key_N_DataStructure Key_N_Data
 8        Dim Key As Int64
 9        Dim Data As Int64
    End Structure

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

    Dim LastTick As Long

    Sub TimerStart()Sub TimerStart(ByVal Text As String)
        Console.Write(Text)
        LastTick = Now.Ticks
    End Sub

    Sub TimerEnd()Sub TimerEnd()
        Dim t As Integer = Now.Ticks - LastTick
        Console.WriteLine(((t) \ 10000).ToString() & " ms")
    End Sub

    Sub Main()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 居然只支持增序 (默认的比较器), 如果要降序的话, 我们得自己写一个比较器.

CODE:
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 对决.

 CODE:
 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.