问题描述
我不明白为什么SortedDictionary的性能比字典约5倍的速度较慢设置和检索值。我期待插入和删除要慢一些，但不能更新或检索。我已经测试的.Net 3.5和.Net 4.0版本编译的code。随机密钥的数组是pre计算的，以确保随机变化是不负责的随机访问的区别。
下面是测试了以下场景。
- 在每个值的使用顺序更新[关键]访问
- 在每个值的使用顺序存取[关键]访问
- 在每个值的使用TryGetValue顺序存取
- 在每个值的使用随机存取[关键]访问
- 在使用TryGetValue每个值的随机访问
任何人都知道为什么性能差异？
请，如果我做错了什么，或愚蠢的，请指出来。
样品code：简单地切换出来字典与SortedDictionary测试的区别
。 const int的numLoops = 100;
const int的numProperties = 30;
const int的numInstances = 1000;
静态无效DictionaryBench（INT numLoops，诠释numValues，诠释numInstances，字符串[] keyArray）
{
秒表SW =新的秒表（）;
双总= 0.0D;
对于（INT J = 0; J＆LT; numLoops; J ++）
{
//sw.Start（）;
字典＆LT;字符串，对象＆gt;原=新字典＆LT;字符串，对象＆gt;（numValues）;
的for（int i = 0; I＆LT; numValues;我++）
{
original.Add（的String.Format（键+ i.ToString（）），Value0：+ i.ToString（））;
}
名单＆LT;字典＆LT;字符串，对象＆gt;＆GT; collectionList =新的名单，其中，字典＆LT;字符串，对象＆gt;＆GT;（numInstances）;
的for（int i = 0; I＆LT; numInstances;我++）
{
collectionList.Add（新字典＆LT;字符串，对象＆gt;（原件））;
}
sw.Start（）;
使用相同的密钥对每个克隆的实例潮头值//设定值
对于（INT K = 0; K＆LT; numInstances; k ++）
{
的for（int i = 0; I＆LT; numValues;我++）
{
collectionList [k]的[键+ i.ToString（）] =值+ k.ToString（）+：+ i.ToString（）;
}
}
//访问的每个唯一值
对象温度;
对于（INT K = 0; K＆LT; numInstances; k ++）
{
的for（int i = 0; I＆LT; numValues;我++）
{
TEMP = collectionList [k]的[键+ i.ToString（）];
}
}
//随机访问
//sw.Start（）;
对于（INT K = 0; K＆LT; numInstances; k ++）
{
的for（int i = 0; I＆LT; numValues;我++）
{
collectionList [k]的.TryGetValue（keyArray [I]中，出温度）;
}
}
sw.Stop（）;
共有+ = sw.ElapsedMilliseconds;
sw.Reset（）;
}
SortedDictionary 使用二进制搜索查找，这是O（日志名词）。照片词典使用哈希表，这是O（1）。
因此，词典提供更快的查找。
的差异会更大一些具有字符串键，这是昂贵的比较。
A 词典将只遍历字符串两次（或者，如果有哈希冲突更多） - 一旦计算哈希值code和一次，以确保它的精确匹配。 A SortedDictionary 将遍历字符串的每次的比较。
I don't understand why the performance of SortedDictionary is approximately 5x slower than Dictionary for setting and retrieving values. I expected inserts and deletes to be slower but not updates or retrieves. I have tested .Net 3.5 and .Net 4.0 release compiled code. An array of random keys was pre-computed to ensure random variations weren't responsible for the differences on random access.
Here are the following scenarios tested.
- Sequential update of each value using [key] accessor
- Sequential access of each value using [key] accessor
- Sequential access of each value using TryGetValue
- Random access of each value using [key] accessor
- Random access of each value using TryGetValue
Anyone know why the performance difference?
Please if I am doing something wrong or stupid please point it out.
Sample Code: Simply switch out Dictionary with SortedDictionary to test the difference.
const int numLoops = 100;
const int numProperties = 30;
const int numInstances = 1000;
static void DictionaryBench(int numLoops, int numValues, int numInstances, string[] keyArray)
{
Stopwatch sw = new Stopwatch();
double total = 0.0d;
for (int j = 0; j < numLoops; j++)
{
//sw.Start();
Dictionary<string, object> original = new Dictionary<string, object>(numValues);
for (int i = 0; i < numValues; i++)
{
original.Add(String.Format("Key" + i.ToString()), "Value0:" + i.ToString());
}
List<Dictionary<string, object>> collectionList = new List<Dictionary<string, object>>(numInstances);
for (int i = 0; i < numInstances; i++)
{
collectionList.Add(new Dictionary<string, object>(original));
}
sw.Start();
//Set values on each cloned instance to uniqe values using the same keys
for (int k = 0; k < numInstances; k++)
{
for (int i = 0; i < numValues; i++)
{
collectionList[k]["Key" + i.ToString()] = "Value" + k.ToString() + ":" + i.ToString();
}
}
//Access each unique value
object temp;
for (int k = 0; k < numInstances; k++)
{
for (int i = 0; i < numValues; i++)
{
temp = collectionList[k]["Key" + i.ToString()];
}
}
//Random access
//sw.Start();
for (int k = 0; k < numInstances; k++)
{
for (int i = 0; i < numValues; i++)
{
collectionList[k].TryGetValue(keyArray[i],out temp);
}
}
sw.Stop();
total += sw.ElapsedMilliseconds;
sw.Reset();
}
SortedDictionary uses a binary search lookup, which is O(log n).Dictionary uses a hashtable, which is O(1).
Therefore, Dictionary gives faster lookups.
The difference will be even greater with string keys, which are costly to compare.
A Dictionary will only iterate the string twice (or more if there are hash collisions) - once to compute the hashcode, and once to ensure that it's an exact match. A SortedDictionary will iterate the string for every comparison.
这篇关于SortedDictionary的意外表现不佳与词典相比，的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！