优化查找:字典键查找与数组索引查找

Question

我正在写一个7卡扑克手评估员作为我的宠物项目之一.在尝试优化速度时(我喜欢挑战),我惊讶地发现,与数组索引查找相比,Dictionary键查找的性能相当慢.

例如,我运行了这个示例代码,列举了所有52个选择7 = 133,784,560个可能的7个牌手:

var intDict = new Dictionary<int, int>();
var intList = new List<int>();
for (int i = 0; i < 100000; i ++)
{
    intDict.Add(i, i);  
    intList.Add(i);
}

int result;

var sw = new Stopwatch();
sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intDict[32131]; // perform C(52,7) dictionary key lookups
sw.Stop();
Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds);

sw.Reset();

sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intList[32131]; // perform C(52,7) array index lookups
sw.Stop();
Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds);

哪个输出:

time for dictionary lookups: 2532 ms
time for array index lookups: 313 ms

是否期望这种行为(性能下降8倍)？IIRC,一个字典平均有O(1)查找,而一个数组有最坏情况的O(1)查找,所以我确实希望数组查找更快,但不是这么多!

我目前正在将字典中的扑克手牌排名存储起来.我想如果这和字典查找一样快,我必须重新考虑我的方法并使用数组,虽然索引排名会有点棘手,我可能不得不问另一个问题.

Answer 1

不要忘记Big-O符号只说明复杂性如何随着大小(等)而增长 - 它没有给出任何涉及的常数因素的指示.这就是为什么有时键甚至线性搜索键比字典查找快,当键数足够少时.在这种情况下,你甚至不用数组进行搜索 - 只是一个直接的索引操作.

对于直接索引查找,数组基本上是理想的 - 它只是一个例子

pointer_into_array = base_pointer + offset * size

(然后指针取消引用.)

执行字典查找相对复杂 - 与存在大量键时(例如)按键进行线性查找相比非常快,但比直接数组查找复杂得多.它必须计算密钥的哈希值,然后确定应该在哪个桶中,可能处理重复的哈希值(或重复的桶),然后检查是否相等.

与往常一样,为作业选择正确的数据结构 - 如果你真的可以通过索引到一个数组(或List<T>),然后是,那将是非常快的.

Answer 2

是否期望这种行为(性能下降8倍)？

为什么不？每个数组查找几乎是临时的/可忽略的,而字典查找可能至少需要一个额外的子程序调用.

它们都是O(1)的意思是,即使你在每个集合中有50倍的项目,性能下降仍然只是它的一个因素(8).

Answer 3

有些东西可能需要一个千年,而且仍然是O(1).

如果您在反汇编窗口中单步执行此代码,您将很快了解其中的区别.