Dictionary<TKey,TValue>,
SortedDictionary<TKey,TValue>, SortedList<TKey,TValue>横向评测
Dictionary<TKey,TValue>、SortedDictionary<TKey,TValue>与SortedList<TKey,TValue>是.NET
Framework的三个泛型的关键字查找的类,都属于System.Collections.Generic命名空间。它们无论是名字还是功能都十分相似,以至于实际运用的时候我们会经常混淆。因此有必要比较一下它们。
1.实现
查阅MSDN得到如下资料:
Dictionary<TKey,
TValue>泛型类提供了从一组键到一组值的映射。字典中的每个添加项都由一个值及其相关联的键组成。通过键来检索值的速度是非常快的,接近于O(1),这是因为Dictionary<TKey,
TValue>类是作为一个哈希表来实现的。
检索速度取决于为TKey指定的类型的哈希算法的质量。
可见,Dictionary<TKey,
TValue>基本上就是一个Hashtable。不过它比Hashtable类快,因为它支持泛型~(稍后我们会用实验证明,即使使用Object类型的Dictionary也比Hashtable稍快)。
SortedDictionary<TKey,
TValue>泛型类是检索运算复杂度为O(log
n)的二叉搜索树,其中n是字典中的元素数。就这一点而言,它与SortedList<TKey,
TValue>泛型类相似。这两个类具有相似的对象模型,并且都具有O(log
n)的检索运算复杂度。这两个类的区别在于内存的使用以及插入和移除元素的速度。
SortedList<TKey,
TValue>使用的内存比SortedDictionary<TKey,
TValue>少。
SortedDictionary<TKey,
TValue>可对未排序的数据执行更快的插入和移除操作:它的时间复杂度为O(log
n),而SortedList<TKey,
TValue>为O(n)。
如果使用排序数据一次性填充列表,则SortedList<TKey,
TValue>比SortedDictionary<TKey,
TValue>快。
每个键/值对都可以作为KeyValuePair<TKey,
TValue>结构进行检索,或作为DictionaryEntry通过非泛型IDictionary接口进行检索。
只要键用作SortedDictionary<TKey,
TValue>中的键,它们就必须是不可变的。SortedDictionary<TKey,
TValue>中的每个键必须是唯一的。键不能为null引用),但是如果值类型TValue为引用类型,该值则可以为空。
SortedDictionary<TKey,
TValue>需要比较器实现来执行键比较。可以使用一个接受comparer参数的构造函数来指定IComparer<T>泛型接口的实现;如果不指定实现,则使用默认的泛型比较器Comparer<T>。如果类型TKey实现IComparable<T>泛型接口,则默认比较器使用该实现。
C#语言的foreach语句需要集合中每个元素的类型。由于SortedDictionary<TKey,
TValue>的每个元素都是一个键/值对,因此元素类型既不是键的类型,也不是值的类型。而是KeyValuePair<TKey,
TValue>类型。
可见,SortedDictionary<TKey,
TValue>类似一个平衡二叉查找树(AVL)。既然是BST,我们当然可以对其进行中序遍历。有两种方法:
1. foreach
2. Object.GetEnumerator
小实验:
CODE:
SortedDictionary<int,int>
TestObject =newSortedDictionary<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>
kvpinTestObject)
{
Console.WriteLine(kvp.Key);
}
得到的顺序是0,1,4,5,7(SortedList<TKey,
TValue>同样)
但是如果把SortedDictionary<TKey,
TValue>换成Dictionary<TKey,
TValue>,结果就是7,0,5,1,4。
另一种遍历方法:
CODE:
SortedDictionary<int,int>.Enumeratorsde
= TestObject.GetEnumerator();
while(sde.MoveNext())
{
Console.WriteLine(sde.Current.Key);
}
SortedDictionary<TKey,
TValue>类和SortedList<TKey,
TValue>类之间的另一个区别是:SortedList<TKey,
TValue>支持通过由Keys和Values属性返回的集合对键和值执行高效的索引检索。访问此属性时无需重新生成列表,因为列表只是键和值的内部数组的包装。
QUOTE:
二叉树的插入操作怎么是O(n)?
网上有一种说法,就是SortedList<TKey,
TValue>内部就是两个数组,插入的时候类似O(n^2)的插入排序(每个动作为O(n)),不过插入有序数据特别快(每个动作变成O(1))。同样的情况出现在删除数据。
CODE:
Randomra
=newRandom();
SortedList<int,int>
TestObject =newSortedList<int,int>();
for(inti
= 1; i <= 1000000; i++)
{
TestObject.Add(i, ra.Next());
}
其中,ra.Next()用来生成随机数。
上述代码执行速度相当快,因为插入的数据的Key值是有序的。
如果把i换成1000000-i,则速度立刻慢得惨不忍睹。
同样的情况出现在把i替换成随机数。在一段时间的等待后出错,因为Key值不能重复。
这样说来,SortedList<TKey,
TValue>不太像二叉树结构.
SortedList<TKey,
TValue>还有一个功能,就是直接访问Key值大小排名为k的Key和Value。
方法(使用属性)是object.Key[k]和object.Value[k)。
这更加印证了网上的说法.
我认为SortedList没什么用-除非是对基本有序的数据,或者对内存非常吝啬。如果仅仅需要在BST上加上查找排名为k的节点的功能,可以使用一个经典算法:在每个节点上加上一个leftsize,储存它左子树的大小。
2.功能
这三个类的功能上面都讲得差不多了。因为实现就决定了功能。这里小结一下。
Dictionary<TKey,
TValue>的功能:
Add,Clear,ContainsKey,ContainsValue,Count(属性),Enumerator(无序),Item(属性),Remove
SortedDictionary<TKey,
TValue>新增的功能:
Enumerator为有序-对应BST的中序遍历。
SortedList<TKey,
TValue>新增的功能:
Capacity(属性)
-毕竟人家是数组
IndexOfKey,IndexOfValue(返回Value对应Key的排名而不是Value的排名)
Keys[k],Values[k]
-返回按照Key排序的数组的第k个元素
3.速度
实践出真知-某名人。
理论和实践不符就是错的-
Thity。
我们的测试程序:
CODE:
staticclassDictionarySpeedTest
{
staticRandomRandomGenerator
=newRandom();
staticList<Key_N_Data>
ArrayListData =newList<Key_N_Data>();
staticDictionary<long,long>
TestObject =newDictionary<long,long>();
publicstructKey_N_Data
{
publiclongKey;
publiclongData;
}
constintITEM_COUNT
= 1000000;
constintTEST_COUNT
= 500000;
staticlongLastTick;
publicstaticvoidTimerStart(stringText)
{
Console.Write(Text);
LastTick =DateTime.Now.Ticks;
}
publicstaticvoidTimerEnd()
{
longt
=DateTime.Now.Ticks - LastTick;
Console.WriteLine(((t)
/ 10000).ToString() +" ms");
}
publicstaticvoidMain()
{
Process.GetCurrentProcess().PriorityClass
=ProcessPriorityClass.High;
Console.WriteLine(TestObject.GetType().ToString());
TimerStart("Generating
data... ");
for(inti
= 1; i <= ITEM_COUNT; i++)
{
Key_N_DataThisKeyData
=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_DataIteminArrayListData)
{
TestObject.Add(Item.Key, Item.Data);
}
TimerEnd();
TimerStart("Test
2: find data test... ");
for(inti
= 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(inti
= 1; i <= TEST_COUNT; i++)
{
TestObject.Remove(ArrayListData[RandomGenerator.Next(0, ITEM_COUNT)].Key);
}
TimerEnd();
Console.Read();
}
}
通过更改TestObject的类型,我们可以很方便地比较这三个类的速度。测试结果:
ADD FIND REMOVE
Dictionary<TKey, TValue> 265ms203ms187ms
SortedDictionary<TKey, TValue> 1843ms 828ms1234ms
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>的随机查找居然比Dictionary<TKey,TValue>和SortedDictionary<TKey,TValue>(Hashtable和BST)还要快。这样说来,SortedList<TKey,TValue>似乎又不是简单的数组了。(不过我仍然觉得它没什么用)
4.小结
如果只是当作索引使用,请用Dictionary<TKey,TValue>。
如果需要查找最小的几个元素,或者需要按顺序遍历元素,就用SortedDictionary<TKey,TValue>。
如果输入/删除的元素是基本增序的,或者访问次数远多于修改次数,或者需要访问第k大的元素,或者对内存吝啬得BT的情况,用SortedList<TKey,TValue>吧。(它居然成使用情况最多的了...
orz)
PS:微软似乎也很吝啬,SortedDictionary<TKey,TValue>居然只支持增序(默认的比较器),如果要降序的话,我们得自己写一个比较器。
CODE:
classMyComparer:Comparer<long>
{
publicoverrideintCompare(longx,longy)
{
returnComparer<long>.Default.Compare(y,
x);
}
}
使用:
SortedList<long,long>
TestObject =newSortedList<long,long>(newMyComparer());
现在我们可以来进行一下刚开始的时候提到的Dictionary<TKey,TValue>(泛型)vs
Hashtable(非泛型)对决。
结果:
ADD FINDREMOVE
Dictionary(Of Long, Long) 271ms 203ms 187ms
Dictionary(Of Object, Object) 468ms 312ms 234ms
Hashtable 859ms 390ms 218ms
结论:最好用Dictionary代替Hashtable。
分享到:
相关推荐
可反转排序的泛型字典类 http://www.cnblogs.com/abatei/archive/2008/02/12/1067166.html
可以帮住那些对数组,泛型,字典表,哈希表用的不是很熟练的朋友作为参考
VTemplate泛型集合字典根据预设键获取值
泛型使用全集(队_栈_字典_列表_对象列表)
c#字典的应用,这是c#中的一个高效的查询手段,利用它你可以提高速度。这段程序,可以起到小例子的作用。帮你更好理解c#字典的应用。
List字典Dictionary泛型集合实例,源码
例如,Swift 的数组和字典类型都是泛型集。你可以创建一个Int数组,也可创建一个String数组,或者甚至于可以是任何其他 Swift 的类型数据数组。同样的,你也可以创建存储任何指定类型的字典(dictionary),而且这些...
可以对自定义的类型进行存取 自定义类型属性可以 包括泛型 数组 字典 字符串 日期 等等,类型存为xml格式;读取的类型集合与存储是完全一致。包括调用方法。消耗无数脑细胞资源分低了对不起自己。
C#命名空间详细分类介绍,方便编程使用,System.Collections //命名空间包含接口和类,这些接口和类定义各种对象(如列表、队列、位数组、哈希表和字典)的集合。 System.Collections.Generic //命名空间包含定义...
第1章 Collections类、泛型类和Timing类概述 第2章 数组和ArrayList 第3章 基础排序算法 第4章 基础查找算法 第5章 栈和队列 第6章 BitArray类 第7章 字符串、String类和StringBuioder类 第8章 模式匹配和文本处理 ...
本文主要介绍了Dictionary集合的7种最基础的用法,包括创建、添加、查找、遍历、删除等方法,程序都是由简入繁,希望能通过阅读简单的示例,给大家一些启发。
一个适合初学者学习的关于文件操作,txt文件操作,实现的对文本的排序,以及添加,功能 文本操作 流操作 排序 泛型 类的封装
这里用到了,泛型,泛型字典,一些控件的操作,split的应用,数组的应用,时间间隔,linkLabel的使用。 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using...
类与对象:理解Object-C中类(Class)和对象(Object)的概念,学习如何定义类、创建对象以及使用对象的属性和方法。 继承与多态:掌握Object-C中的继承和多态机制,了解子类如何继承父类的属性和方法,并实现自己...
一个Node.js模块,可从Object数组创建通用类型对象的数组或字典 安装 npm install @caliatys/array-typer --save 用法 Java脚本 设置示例 // Let's create our own object type let MyObject = /** @class */ ( ...
SortedDictionary 泛型类是检索运算复杂度为 O(log n) 的二叉搜索树,其中 n 是字典中的元素数。就这一点而言,它与 SortedList 泛型类相似。这两个类具有相似的对象模型,并且都具有 O(log n) 的检索运算...
非阻塞非阻塞字典的实现。 概述非阻塞词典: NonBlocking词典与ConcurrentDictionary具有相同的API。 在任何操作(包括获取,添加,删除,内部调整大小等)期间都不会获取任何锁定。 虽然多个线程访问NonBlocking...
泛型编程允许程序员编写一个类或一种方法,并且把它用于众多数据类型。泛型编程是C#语言一种重要的新特性(在C#2.0以及更高版本中可用)。这种特性是如此重要以至于在System.Collections.Generic命名空间中存在一个...
11.9 从泛型类中继承 247 11.10 泛型运算符 248 11.11 泛型结构 250 11.12 定义泛型接口 250 11.13 定义泛型方法 251 11.14 定义泛型委托 253 11.15 独立实践 253 12 反射 254 12.1 定制特性 254 12.2 编写...