35

我正在编写一个 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) 查找，所以我确实希望数组查找更快，但不会这么快！

我目前将扑克手牌排名存储在字典中。我想如果这与字典查找一样快，我必须重新考虑我的方法并改用数组，尽管索引排名会有点棘手，我可能不得不问另一个问题。

4

7 回答 7

67

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

对于直接索引查找，数组基本上是理想的——这只是

pointer_into_array = base_pointer + offset * size

（然后是指针取消引用。）

执行字典查找相对复杂 - 与（例如）在有很多键时按键进行线性查找相比非常快，但比直接数组查找要复杂得多。它必须计算密钥的哈希，然后计算出应该在哪个桶中，可能处理重复的哈希（或重复的桶），然后检查是否相等。

与往常一样，为这项工作选择正确的数据结构——如果你真的可以只对数组（或List<T>）进行索引，那么是的，那将是非常快的。

于 2009-05-25T21:09:02.410 回答
8

是否会出现这种行为（性能下降 8 倍）？

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

它们都是 O(1) 的意义在于，即使每个集合中有 50 倍以上的项目，性能下降仍然只是它 (8) 的一个因素。

于 2009-05-25T21:13:34.477 回答
6

有些事情可能需要一千年，但仍然是 O(1)。

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

于 2009-05-26T01:03:45.293 回答
4

当键空间非常大并且无法映射成稳定的有序顺序时，字典结构最有用。如果您可以将键转换为相对较小范围内的简单整数，那么您将很难找到比数组性能更好的数据结构。

On an implementation note; in .NET, dictionaries are essentially hashables. You can somewhat improve their key-lookup performance by ensuring that your keys hash into a large space of unique values. It looks like in your case, you are using a simple integer as a key (which I believe hashes to its own value) - so that may be the best you can do.

于 2009-05-26T02:43:13.407 回答
3

数组查找是您可以做的最快的事情 - 基本上它只是从数组的开头到您想要查找的元素的一点指针算术。另一方面，字典查找可能会慢一些，因为它需要进行散列处理并关注找到正确的存储桶。虽然预期的运行时间也是 O(1) - 算法常数更大，所以它会更慢。

于 2009-05-25T21:09:56.963 回答
2

欢迎使用 Big-O 表示法。您始终必须考虑涉及一个恒定的因素。

做一个字典查找当然比数组查找要昂贵得多。

Big-O 只告诉您算法如何扩展。将查找次数加倍并查看数字如何变化：两者都应该花费大约两倍的时间。

于 2009-05-25T21:10:19.943 回答
1

从 Dictionary 中检索元素的成本是 O(1)，但这是因为字典是作为哈希表实现的 - 所以您必须首先计算哈希值才能知道要返回哪个元素。哈希表通常效率不高 - 但它们适用于大型数据集或具有大量唯一哈希值的数据集。

List（除了是一个用来描述数组而不是链表的垃圾词！）会更快，因为它将通过直接计算您想要返回的元素来返回值。

于 2009-05-25T21:18:37.977 回答