与平面阵列相比,.Net中的简单字典查找速度慢

Question

我发现,与平面阵列访问相比,字典查找可能会非常慢.知道为什么吗？我正在使用Ants Profiler进行性能测试.这是一个重现问题的示例函数:

    private static void NodeDisplace()
    {
        var nodeDisplacement = new Dictionary<double, double[]>();

        var times = new List<double>();
        for (int i = 0; i < 6000; i++)
        {
            times.Add(i * 0.02);
        }
        foreach (var time in times)
        {
            nodeDisplacement.Add(time, new double[6]);
        }

        var five = 5;
        var six = 6;
        int modes = 10;
        var arrayList = new double[times.Count*6];
        for (int i = 0; i < modes; i++)
        {
            int k=0;
            foreach (var time in times)
            {
                for (int j = 0; j < 6; j++)
                {

                    var simpelCompute = five * six;  // 0.027 sec
                    nodeDisplacement[time][j] = simpelCompute;  //0.403 sec
                    arrayList[6*k+j] = simpelCompute;  //0.0278 sec
                }

                k++;
            }
        }
    }

注意平面阵列访问和字典访问之间的相对大小？在考虑了数组索引操作(6*k+j)之后,平面数组比字典访问快了约20倍(0.403/0.0278 ).

虽然听起来很奇怪,但字典查找占据了我的大部分时间,我必须优化它.

Answer 1

是的,我并不感到惊讶.词典的意思是它们习惯于查找任意键.考虑单个阵列解除引用会发生什么:

• 检查边界
• 按元素大小乘以索引
• 向索引添加索引

非常,非常快.现在进行字典查找(非常粗略;取决于实现):

• 潜在地检查无效的关键
• 获取密钥的哈希码
• 找到该哈希码的正确插槽(可能是"mod prime"操作)
• 可能取消引用数组元素以查找该槽的信息
• 比较哈希码
• 如果哈希码匹配,则比较相等(并可能继续下一个哈希码匹配)

如果你有"键" 可以很容易地用作数组索引(例如连续的整数,或者可以很容易地映射到连续整数的东西),那么这将是非常非常快的.这不是哈希表的主要用例.它们适用于无法轻易映射的情况 - 例如通过字符串或任意 double值查找(而不是均匀间隔的双精度,因此可以轻松映射到整数).

我会说你的标题是误导性的 - 这不是字典查找很慢,而是当数组是一种更合适的方法时,它们的速度非常快.