c# - 优化查找 : Dictionary key lookups vs. 数组索引查找

Question

我正在编写一个 7 张牌的扑克手牌评估程序，作为我最喜欢的项目之一。在尝试优化其速度(我喜欢挑战)时，我震惊地发现字典键查找的性能与数组索引查找相比相当慢。

例如，我运行了这个示例代码，它列举了所有 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

(然后是指针解引用。)

执行字典查找相对复杂 - 与(比如说)在有很多键的情况下按键进行线性查找相比非常快，但比直接数组查找复杂得多。它必须计算 key 的哈希值，然后计算出应该在哪个桶中，可能会处理重复的哈希值(或重复的桶)，然后检查是否相等。

一如既往，为工作选择正确的数据结构 - 如果您真的可以通过索引数组(或 List<T> )来摆脱困境，那么是的，那将快得令人眼花缭乱。