Dictionary<TKey,TValue>, SortedDictionary<TKey,TValue>, SortedList<TKey,TValue>橫向評(píng)測(cè)
創(chuàng)新互聯(lián)公司專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù),包含不限于網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)、雨湖網(wǎng)絡(luò)推廣、成都微信小程序、雨湖網(wǎng)絡(luò)營(yíng)銷、雨湖企業(yè)策劃、雨湖品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等,從售前售中售后,我們都將竭誠(chéng)為您服務(wù),您的肯定,是我們大的嘉獎(jiǎng);創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供雨湖建站搭建服務(wù),24小時(shí)服務(wù)熱線:13518219792,官方網(wǎng)址:muchs.cnDictionary<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)的鍵組成。通過鍵來檢索值的速度是非??斓模咏贠(1),這是因?yàn)镈ictionary<TKey, TValue>類是作為一個(gè)哈希表來實(shí)現(xiàn)的。
檢索速度取決于為TKey指定的類型的哈希算法的質(zhì)量。
可見,Dictionary<TKey, TValue>基本上就是一個(gè)Hashtable。不過它比Hashtable類快,因?yàn)樗С址盒蛜(稍后我們會(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)镵ey值不能重復(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。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn,海內(nèi)外云服務(wù)器15元起步,三天無理由+7*72小時(shí)售后在線,公司持有idc許可證,提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案,具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì),專為企業(yè)上云打造定制,能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
本文標(biāo)題:泛型字典類比較-創(chuàng)新互聯(lián)
URL網(wǎng)址:http://muchs.cn/article26/degojg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供軟件開發(fā)、營(yíng)銷型網(wǎng)站建設(shè)、網(wǎng)站制作、品牌網(wǎng)站設(shè)計(jì)、靜態(tài)網(wǎng)站、搜索引擎優(yōu)化
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容