泛型字典类比较-创新互联
Dictionary
Dictionary
1. 实现
查阅 MSDN 得到如下资料:
Dictionary
检索速度取决于为TKey指定的类型的哈希算法的质量。
可见,Dictionary
SortedDictionary
SortedList
SortedDictionary
如果使用排序数据一次性填充列表,则SortedList
每个键/值对都可以作为KeyValuePair
只要键用作SortedDictionary
SortedDictionary
C#语言的foreach语句需要集合中每个元素的类型。由于SortedDictionary
可见,SortedDictionary
1. foreach
2. Object.GetEnumerator
小实验:
CODE:
SortedDictionary
TestObject.Add(7, 2);
TestObject.Add(0, 1);
TestObject.Add(5, 3);
TestObject.Add(1, 1);
TestObject.Add(4, 4);
foreach (KeyValuePair
{
Console.WriteLine(kvp.Key);
}
得到的顺序是0,1,4,5,7(SortedList
但是如果把SortedDictionary
另一种遍历方法:
CODE:
SortedDictionary
while (sde.MoveNext())
{
Console.WriteLine(sde.Current.Key);
}
SortedDictionary
QUOTE:
二叉树的插入操作怎么是 O(n)?
网上有一种说法, 就是SortedList
CODE:
Random ra = new Random();
SortedList
for (int i = 1; i <= 1000000; i++)
{
TestObject.Add(i, ra.Next());
}
其中,ra.Next()用来生成随机数。
上述代码执行速度相当快,因为插入的数据的Key值是有序的。
如果把i换成1000000-i,则速度立刻慢得惨不忍睹。
同样的情况出现在把i替换成随机数。在一段时间的等待后出错,因为Key值不能重复。
这样说来,SortedList
SortedList
方法(使用属性)是object.Key[k]和object.Value[k)。
这更加印证了网上的说法.
我认为SortedList没什么用 - 除非是对基本有序的数据,或者对内存非常吝啬。如果仅仅需要在BST上加上查找排名为k的节点的功能,可以使用一个经典算法:在每个节点上加上一个leftsize,储存它左子树的大小。
2. 功能
这三个类的功能上面都讲得差不多了。因为实现就决定了功能。这里小结一下。
Dictionary
Add,Clear,ContainsKey,ContainsValue,Count(属性),Enumerator(无序),Item(属性), Remove
SortedDictionary
Enumerator为有序 - 对应BST的中序遍历。
SortedList
Capacity(属性) - 毕竟人家是数组
IndexOfKey,IndexOfValue(返回Value对应Key的排名而不是 Value 的排名)
Keys[k],Values[k] - 返回按照Key排序的数组的第k个元素
3. 速度
实践出真知 - 某名人。
理论和实践不符就是错的 - Thity。
我们的测试程序:
CODE:
static class DictionarySpeedTest
{
static Random RandomGenerator = new Random();
static List
static 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的类型,我们可以很方便地比较这三个类的速度。测试结果:
ADD FIND REMOVE
Dictionary
SortedDictionary
SortedList
我们把ITEM_COUNT和TEST_COUNT都减小10倍:
ADD FIND REMOVE
Dictionary
SortedDictionary
SortedList
SortedList
4. 小结
如果只是当作索引使用,请用Dictionary
如果需要查找最小的几个元素,或者需要按顺序遍历元素,就用SortedDictionary
如果输入/删除的元素是基本增序的,或者访问次数远多于修改次数,或者需要访问第k大的元素,或者对内存吝啬得BT的情况,用SortedList
PS: 微软似乎也很吝啬,SortedDictionary
CODE:
class MyComparer : Comparer
{
public override int Compare(long x, long y)
{
return Comparer
}
}
使用:
SortedList
现在我们可以来进行一下刚开始的时候提到的Dictionary
结果:
ADD FIND REMOVE
Dictionary(Of Long, Long) 271ms 203ms 187ms
Dictionary(Of Object, Object) 468ms 312ms 234ms
Hashtable 859ms 390ms 218ms
结论: 最好用Dictionary代替Hashtable。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
文章名称:泛型字典类比较-创新互联
网页网址:http://myzitong.com/article/degojg.html