Dictionary, SortedDictionary, SortedList橫向評(píng)測

創(chuàng)新互聯(lián)公司專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)、雨湖網(wǎng)絡(luò)推廣、成都微信小程序、雨湖網(wǎng)絡(luò)營銷、雨湖企業(yè)策劃、雨湖品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供雨湖建站搭建服務(wù)，24小時(shí)服務(wù)熱線：13518219792，官方網(wǎng)址：www.cdcxhl.com

Dictionary、SortedDictionary與 SortedList是.NET Framework的三個(gè)泛型的關(guān)鍵字查找的類，都屬于System.Collections.Generic命名空間。它們無論是名字還是功能都十分相似，以至于實(shí)際運(yùn)用的時(shí)候我們會(huì)經(jīng)常混淆。因此有必要比較一下它們。

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

查閱 MSDN 得到如下資料:

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

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

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

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

SortedList使用的內(nèi)存比SortedDictionary少。

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

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

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

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

SortedDictionary需要比較器實(shí)現(xiàn)來執(zhí)行鍵比較。可以使用一個(gè)接受 comparer參數(shù)的構(gòu)造函數(shù)來指定IComparer泛型接口的實(shí)現(xiàn)；如果不指定實(shí)現(xiàn)，則使用默認(rèn)的泛型比較器Comparer。如果類型TKey實(shí)現(xiàn)IComparable泛型接口，則默認(rèn)比較器使用該實(shí)現(xiàn)。

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

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

1. foreach

2. Object.GetEnumerator

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

CODE:

SortedDictionary TestObject = new SortedDictionary();

TestObject.Add(7, 2);

TestObject.Add(0, 1);

TestObject.Add(5, 3);

TestObject.Add(1, 1);

TestObject.Add(4, 4);

foreach (KeyValuePair kvp in TestObject)

{

Console.WriteLine(kvp.Key);

}

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

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

另一種遍歷方法:

CODE:

SortedDictionary.Enumerator sde = TestObject.GetEnumerator();

while (sde.MoveNext())

{

Console.WriteLine(sde.Current.Key);

}

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

QUOTE:

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

網(wǎng)上有一種說法, 就是SortedList內(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 TestObject = new SortedList();

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)镵ey值不能重復(fù)。

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

SortedList還有一個(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的功能:

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

SortedDictionary新增的功能：

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

SortedList新增的功能:

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

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

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

3. 速度

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

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

我們的測試程序:

CODE:

static class DictionarySpeedTest

{

static Random RandomGenerator = new Random();

static List ArrayListData = new List();

static Dictionary TestObject = new Dictionary();

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è)類的速度。測試結(jié)果：

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

4. 小結(jié)

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

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

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

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

CODE:

class MyComparer : Comparer

{

public override int Compare(long x, long y)

{

return Comparer.Default.Compare(y, x);

}

}

使用：

SortedList TestObject = new SortedList(new MyComparer());

現(xiàn)在我們可以來進(jìn)行一下剛開始的時(shí)候提到的Dictionary（泛型）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。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站欄目：泛型字典類比較-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://weahome.cn/article/degojg.html