我正在一个O(n^2)的循环中进行Dictionary<>
查找,但速度并不快。有人能解释一下Dictionary<>
是如何实现的吗?在通过分析器运行我的代码并确定Dictionary查找占用了大量CPU时间后,我使用隔离测试案例测试Dictionary性能。我的测试代码如下:
Int32[] keys = new Int32[10] { 38784, 19294, 109574, 2450985, 5, 398, 98405, 12093, 909802, 38294394 };
Dictionary<Int32, MyData> map = new Dictionary<Int32, MyData>();
//Add a bunch of things to map
timer.Start();
Object item;
for (int i = 0; i < 1000000; i++)
{
for (int j = 0; j < keys.Length; j++)
{
bool isFound = map.ContainsKey(keys[j]);
if (isFound)
{
item = map[keys[j]];
}
}
}
timer.Stop();
ContainsKey和map[]是两个很慢的部分(同样慢)… 如果我添加一个TryGetValue,它的速度几乎与ContainsKey相同。以下是一些有趣的事实…
一个Dictionary<Guid, T>大约比一个Dictionary<Int32, T>慢两倍。Dictionary<String, T>大约比Guid dictionary慢两倍。与使用Ints相比,Dictionary<Byte, T>要快50%左右。这让我相信Dictionary正在做一个O(log n)二进制搜索来查找键,并且键上的比较运算符是瓶颈。出于某种原因,我不认为它被实现为Hashtable,因为.NET已经有一个Hashtable类,在我的经验中它甚至比Dictionary还要慢。
我正在构建的字典每次只能被一个线程访问,所以读取锁定不是问题。RAM也不是问题。字典很可能只有大约10个桶,但是每个桶可以指向约2,000个可能的内容之一。有人有关于如何使其更快的反馈吗?谢谢!
Mike