泛型字典類比較

Dictionary<TKey,TValue>, SortedDictionary<TKey,TValue>, SortedList<TKey,TValue>橫向評(píng)測(cè)

Dictionary<TKey,TValue>、SortedDictionary<TKey,TValue>與 SortedList<TKey,TValue>是.NET Framework的三個(gè)泛型的關(guān)鍵字查找的類，都屬于System.Collections.Generic命名空間。它們無論是名字還是功能都十分相似，以至于實(shí)際運(yùn)用的時(shí)候我們會(huì)經(jīng)?；煜Ｒ虼擞斜匾容^一下它們。

1. 實(shí)現(xiàn)

查閱 MSDN 得到如下資料:

Dictionary<TKey, TValue>泛型類提供了從一組鍵到一組值的映射。字典中的每個(gè)添加項(xiàng)都由一個(gè)值及其相關(guān)聯(lián)的鍵組成。通過鍵來檢索值的速度是非?？斓?，接近于O(1)，這是因?yàn)?/span>Dictionary<TKey, TValue>類是作為一個(gè)哈希表來實(shí)現(xiàn)的。

檢索速度取決于為TKey指定的類型的哈希算法的質(zhì)量。

可見，Dictionary<TKey, TValue>基本上就是一個(gè)Hashtable。不過它比Hashtable類快，因?yàn)樗С址盒?/span>~(稍后我們會(huì)用實(shí)驗(yàn)證明，即使使用Object類型的Dictionary也比 Hashtable稍快)。

SortedDictionary<TKey, TValue>泛型類是檢索運(yùn)算復(fù)雜度為O(log n)的二叉搜索樹，其中n是字典中的元素?cái)?shù)。就這一點(diǎn)而言，它與SortedList<TKey, TValue>泛型類相似。這兩個(gè)類具有相似的對(duì)象模型，并且都具有O(log n)的檢索運(yùn)算復(fù)雜度。這兩個(gè)類的區(qū)別在于內(nèi)存的使用以及插入和移除元素的速度。

SortedList<TKey, TValue>使用的內(nèi)存比SortedDictionary<TKey, TValue>少。

SortedDictionary<TKey, TValue>可對(duì)未排序的數(shù)據(jù)執(zhí)行更快的插入和移除操作：它的時(shí)間復(fù)雜度為O(log n)，而SortedList<TKey, TValue>為O(n)。

如果使用排序數(shù)據(jù)一次性填充列表，則SortedList<TKey, TValue>比 SortedDictionary<TKey, TValue>快。

每個(gè)鍵/值對(duì)都可以作為KeyValuePair<TKey, TValue>結(jié)構(gòu)進(jìn)行檢索，或作為 DictionaryEntry通過非泛型IDictionary接口進(jìn)行檢索。

只要鍵用作SortedDictionary<TKey, TValue>中的鍵，它們就必須是不可變的。SortedDictionary<TKey, TValue>中的每個(gè)鍵必須是唯一的。鍵不能為null引用），但是如果值類型TValue為引用類型，該值則可以為空。

SortedDictionary<TKey, TValue>需要比較器實(shí)現(xiàn)來執(zhí)行鍵比較?？梢允褂靡粋€(gè)接受 comparer參數(shù)的構(gòu)造函數(shù)來指定IComparer<T>泛型接口的實(shí)現(xiàn)；如果不指定實(shí)現(xiàn)，則使用默認(rèn)的泛型比較器Comparer<T>。如果類型TKey實(shí)現(xiàn)IComparable<T>泛型接口，則默認(rèn)比較器使用該實(shí)現(xiàn)。

C#語言的foreach語句需要集合中每個(gè)元素的類型。由于SortedDictionary<TKey, TValue>的每個(gè)元素都是一個(gè)鍵/值對(duì)，因此元素類型既不是鍵的類型，也不是值的類型。而是KeyValuePair<TKey, TValue>類型。

可見，SortedDictionary<TKey, TValue>類似一個(gè)平衡二叉查找樹(AVL)。既然是 BST，我們當(dāng)然可以對(duì)其進(jìn)行中序遍歷。有兩種方法:

1. foreach

2. Object.GetEnumerator

小實(shí)驗(yàn):

CODE:

SortedDictionary<int, int> TestObject = new SortedDictionary<int, int>();

TestObject.Add(7, 2);

TestObject.Add(0, 1);

TestObject.Add(5, 3);

TestObject.Add(1, 1);

TestObject.Add(4, 4);

foreach (KeyValuePair<int, int> kvp in TestObject)

{

Console.WriteLine(kvp.Key);

}

得到的順序是0,1,4,5,7(SortedList<TKey, TValue>同樣)

但是如果把SortedDictionary<TKey, TValue>換成Dictionary<TKey, TValue>, 結(jié)果就是7,0,5,1,4。

另一種遍歷方法:

CODE:

SortedDictionary<int, int>.Enumerator sde = TestObject.GetEnumerator();

while (sde.MoveNext())

{

Console.WriteLine(sde.Current.Key);

}

SortedDictionary<TKey, TValue>類和SortedList<TKey, TValue>類之間的另一個(gè)區(qū)別是：SortedList<TKey, TValue>支持通過由Keys和Values屬性返回的集合對(duì)鍵和值執(zhí)行高效的索引檢索。訪問此屬性時(shí)無需重新生成列表，因?yàn)榱斜碇皇擎I和值的內(nèi)部數(shù)組的包裝。

QUOTE:

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

網(wǎng)上有一種說法, 就是SortedList<TKey, TValue>內(nèi)部就是兩個(gè)數(shù)組, 插入的時(shí)候類似O(n^2)的插入排序(每個(gè)動(dòng)作為O(n))，不過插入有序數(shù)據(jù)特別快(每個(gè)動(dòng)作變成O(1))。同樣的情況出現(xiàn)在刪除數(shù)據(jù)。

CODE:

Random ra = new Random();

SortedList<int, int> TestObject = new SortedList<int, int>();

for (int i = 1; i <= 1000000; i++)

{

TestObject.Add(i, ra.Next());

}

其中，ra.Next()用來生成隨機(jī)數(shù)。

上述代碼執(zhí)行速度相當(dāng)快，因?yàn)椴迦氲臄?shù)據(jù)的Key值是有序的。

如果把i換成1000000-i，則速度立刻慢得慘不忍睹。

同樣的情況出現(xiàn)在把i替換成隨機(jī)數(shù)。在一段時(shí)間的等待后出錯(cuò)，因?yàn)?/span>Key值不能重復(fù)。

這樣說來，SortedList<TKey, TValue>不太像二叉樹結(jié)構(gòu).

SortedList<TKey, TValue>還有一個(gè)功能，就是直接訪問Key值大小排名為k的Key 和Value。

方法(使用屬性)是object.Key[k]和object.Value[k)。

這更加印證了網(wǎng)上的說法.

我認(rèn)為SortedList沒什么用 - 除非是對(duì)基本有序的數(shù)據(jù)，或者對(duì)內(nèi)存非常吝嗇。如果僅僅需要在BST上加上查找排名為k的節(jié)點(diǎn)的功能，可以使用一個(gè)經(jīng)典算法：在每個(gè)節(jié)點(diǎn)上加上一個(gè)leftsize，儲(chǔ)存它左子樹的大小。

2. 功能

這三個(gè)類的功能上面都講得差不多了。因?yàn)閷?shí)現(xiàn)就決定了功能。這里小結(jié)一下。

Dictionary<TKey, TValue>的功能:

Add，Clear，ContainsKey，ContainsValue，Count（屬性），Enumerator(無序)，Item(屬性)， Remove

SortedDictionary<TKey, TValue>新增的功能：

Enumerator為有序 - 對(duì)應(yīng)BST的中序遍歷。

SortedList<TKey, TValue>新增的功能:

Capacity(屬性) - 畢竟人家是數(shù)組

IndexOfKey，IndexOfValue(返回Value對(duì)應(yīng)Key的排名而不是 Value 的排名)

Keys[k]，Values[k] - 返回按照Key排序的數(shù)組的第k個(gè)元素

3. 速度

實(shí)踐出真知 - 某名人。

理論和實(shí)踐不符就是錯(cuò)的 - Thity。

我們的測(cè)試程序:

CODE:

static class DictionarySpeedTest

{

static Random RandomGenerator = new Random();

static List<Key_N_Data> ArrayListData = new List<Key_N_Data>();

static Dictionary<long, long> TestObject = new Dictionary<long, long>();

public struct Key_N_Data

{

public long Key;

public long Data;

}

const int ITEM_COUNT = 1000000;

const int TEST_COUNT = 500000;

static long LastTick;

public static void TimerStart(string Text)

{

Console.Write(Text);

LastTick = DateTime.Now.Ticks;

}

public static void TimerEnd()

{

long t = DateTime.Now.Ticks - LastTick;

Console.WriteLine(((t) / 10000).ToString() + " ms");

}

public static void Main()

{

Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;

Console.WriteLine(TestObject.GetType().ToString());

TimerStart("Generating data... ");

for (int i = 1; i <= ITEM_COUNT; i++)

{

Key_N_Data ThisKeyData = default(Key_N_Data);

ThisKeyData.Key = ((long)RandomGenerator.Next() << 31) | RandomGenerator.Next();

ThisKeyData.Data = ((long)RandomGenerator.Next() << 31) | RandomGenerator.Next();

ArrayListData.Add(ThisKeyData);

}

TimerEnd();

TimerStart("Test 1: add data test... ");

foreach (Key_N_Data Item in ArrayListData)

{

TestObject.Add(Item.Key, Item.Data);

}

TimerEnd();

TimerStart("Test 2: find data test... ");

for (int i = 1; i <= TEST_COUNT; i++)

{

{

if (TestObject[ArrayListData[RandomGenerator.Next(0, ITEM_COUNT)].Key] != ArrayListData[RandomGenerator.Next(0, ITEM_COUNT)].Data)

Console.WriteLine("Error!");

}

}

TimerEnd();

TimerStart("Test 3: remove data test...");

for (int i = 1; i <= TEST_COUNT; i++)

{

TestObject.Remove(ArrayListData[RandomGenerator.Next(0, ITEM_COUNT)].Key);

}

TimerEnd();

Console.Read();

}

}

通過更改TestObject的類型，我們可以很方便地比較這三個(gè)類的速度。測(cè)試結(jié)果：

                  ADD    FIND   REMOVE

Dictionary<TKey, TValue>       265ms  203ms  187ms

SortedDictionary<TKey, TValue> 1843ms 828ms  1234ms

SortedList<TKey, TValue>       N/A

我們把ITEM_COUNT和TEST_COUNT都減小10倍：

                  ADD    FIND   REMOVE

Dictionary<TKey,TValue>       15ms   31ms   15ms

SortedDictionary<TKey,TValue> 93ms   46ms   38ms

SortedList<TKey,TValue>       8031ms 15ms   6046ms

SortedList<TKey,TValue>的隨機(jī)查找居然比Dictionary<TKey,TValue>和SortedDictionary<TKey,TValue>(Hashtable和BST)還要快。這樣說來，SortedList<TKey,TValue>似乎又不是簡(jiǎn)單的數(shù)組了。(不過我仍然覺得它沒什么用)

4. 小結(jié)

如果只是當(dāng)作索引使用，請(qǐng)用Dictionary<TKey,TValue>。

如果需要查找最小的幾個(gè)元素，或者需要按順序遍歷元素，就用SortedDictionary<TKey,TValue>。

如果輸入/刪除的元素是基本增序的，或者訪問次數(shù)遠(yuǎn)多于修改次數(shù)，或者需要訪問第k大的元素，或者對(duì)內(nèi)存吝嗇得BT的情況，用SortedList<TKey,TValue>吧。(它居然成使用情況最多的了... orz)

PS: 微軟似乎也很吝嗇，SortedDictionary<TKey,TValue>居然只支持增序(默認(rèn)的比較器)，如果要降序的話，我們得自己寫一個(gè)比較器。

CODE:

class MyComparer : Comparer<long>

{

public override int Compare(long x, long y)

{

return Comparer<long>.Default.Compare(y, x);

}

}

使用：

SortedList<long, long> TestObject = new SortedList<long, long>(new MyComparer());

現(xiàn)在我們可以來進(jìn)行一下剛開始的時(shí)候提到的Dictionary<TKey,TValue>（泛型）vs Hashtable（非泛型）對(duì)決。

結(jié)果：

ADD   FIND  REMOVE

Dictionary(Of Long, Long)     271ms 203ms 187ms

Dictionary(Of Object, Object) 468ms 312ms 234ms

Hashtable                         859ms 390ms 218ms

結(jié)論: 最好用Dictionary代替Hashtable。