优化查找：字典键查找 vs. 数组索引查找

Question

优化查找：字典键查找 vs. 数组索引查找

36

我正在编写一个七张扑克牌手的评估程序作为我的个人项目之一。在试图优化其速度时（我喜欢挑战），我惊讶地发现，与数组索引查找相比，字典键查找的性能非常慢。

例如，我运行了这个示例代码，它枚举了所有 52 张牌中选出 7 张牌的可能情况，总共有133,784,560种不同的情况：

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倍）？如果我没记错，一个字典平均查找的时间复杂度为O(1)，而数组最坏情况下查找的时间复杂度也是O(1)，所以我确实希望数组的查找速度更快，但并不会快到这个程度！

目前，我正在使用字典来存储扑克牌手牌等级。如果这已经是字典查找的最快速度，那么我必须重新思考我的方法并改用数组，虽然索引等级可能有点棘手，我可能还需要问另一个问题。

- snazzer

23

即使字典查找每个项目总是需要1小时才能完成，而且总是需要1小时，即使另一种查找类型（例如数组查找）只需1毫秒，并且也是O(1)，它仍然是O(1)。您只能使用大O符号来比较复杂度，不要将其替代实际测量代码的运行性能特征。 - Lasse V. Karlsen

我认为“复杂性”不是正确的词，大O符号告诉你它如何随着项目数量扩展。O(1)告诉你锁定是恒定的，也就是说，随着集合的增长，查找不会变慢。然而，查找可以具有非常高的复杂度，仍然是O(1)，例如字典的情况，或者它们可以具有非常低的复杂度，并且是O(1)，例如数组查找。 - trampster

1

我很想看看你的方法与我的OneJoker库相比如何。它针对5张牌的手牌进行了优化，但也可以处理7张牌，并且我的查找表只有约1MB，而你的可能接近1GB。 - Lee Daniel Crocker

7个回答

8

这种行为是否是预期的（性能降低了8倍）？

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

它们都是O(1)的意思是即使每个集合中有50倍的项目，性能下降仍然只是它所影响的倍数（8）。

- ChrisW

1

不完全正确。实际上，根本不应该有性能下降！这就是O(1)的真正意义。字典确实有一个小注脚，它说：如果哈希函数产生了太多的重复项，或者桶的数量太少，那么性能将会下降。 - Disillusioned

@CraigYoung 我的意思是，一个实现方式（数组）和另一个实现方式（字典）之间的性能差异应该保持恒定（8倍因子），与大小无关。 - ChrisW

我理解了你的观点。我相信你误解了我的观点。声称任何O(1)算法存在任何性能下降都是完全错误的！此外，你所归属于两个不同的O(1)算法的属性对于任何相同阶级别的两个算法都是正确的。（即2个O(n^2)算法也会因为独立于大小的常数因素而有所不同；2个O(n!)算法也是如此）。所以你完全错过了任何东西都是O(1)的真正意义。 - Disillusioned

@CraigYoung 我并不是在说随着规模增加性能会下降。如果你有两种实现（数组和字典），并且它们都是 O(1) 的，如果字典比数组慢 8 倍，当它们都包含例如 10 个项目时，那么我预测当它们都包含 100 或 1000 个项目时，字典仍然比数组慢 8 倍。 - ChrisW

你可能不是想说性能会降低，但这正是你的回答所表明的。引用：“如果每个集合中有50倍更多的项，则性能将下降”。假设字典对于100个项的性能为8ms，而数组为1ms，则对于1000个项，它们的性能分别为8ms和1ms。或者对于1000000个项，它们的性能分别为8ms和1ms！（显然，如果性能根本不改变，那么字典“仍然”比数组慢8倍。） - Disillusioned

4

“减少”这个词出现在原帖中，并被我在回答中引用了。所讨论的“减少”是数组和字典之间速度差异的减小，而不是存储更多项时速度差异的减小。 - ChrisW

7

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

如果您在反汇编窗口中逐步执行此代码，您很快就会理解其中的区别。

- Mike Dunlavey

4

是的。编写O(1)算法的简单方法是预先计算最坏情况（即n的最大值），然后即使对于集合中最简单的元素（例如第一个元素），也运行相同时间的算法。集合保持O(1)。你甚至可能会以O(1)的速度被公司开除 :) - nawfal

4

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

在实现方面，在.NET中，字典基本上是可哈希的。通过确保您的键哈希到大量唯一值的空间中，您可以在某种程度上提高它们的键查找性能。看起来在您的情况下，您正在使用一个简单的整数作为键（我认为哈希到其自身的值），因此那可能是您所能做的最好的事情。

- LBushkin

3

数组查找是你可以做的最快的事情 - 基本上它只是一个指针算术的单个位，从数组的开头到你想要找到的元素。另一方面，字典查找可能会比较慢，因为它需要进行哈希和关注找到正确的桶。尽管预期运行时间也是O（1） - 但算法常数更大，所以它会更慢。

- 1800 INFORMATION

2

欢迎来到大O符号。您始终需要考虑到涉及一个常数因素。

当然，执行一次字典查找比数组查找要昂贵得多。

大O仅告诉您算法的缩放方式。将查找量加倍，观察数字如何变化：两者应该花费大约两倍的时间。

- ebo

3

并非完全如此。将 O(n) 搜索算法的查找次数翻倍也会导致它花费两倍的时间。大 O 表示法确实告诉您算法的规模。但问题不在于查找次数，而在于搜索的数据量...... 因此：如果您将数据量翻倍：两个 O(1) 查找应该与之前的时间差不多。但是一个 O(n) 查找应该比之前要用两倍的时间。 - Disillusioned

1

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

列表（除了用于描述数组而不是链表的垃圾词语之外！）将更快，因为它将通过直接计算要返回的元素来返回该值。

- gbjbaanb

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jon Skeet · Accepted Answer

不要忘记，大O符号只是说明了复杂度随着输入规模的增长而增长的趋势 - 它并没有给出有关涉及的常数因子的任何指示。这就是为什么有时候即使线性查找键比使用字典查找更快，当键数量足够少的时候。在这种情况下，你甚至都不需要对数组进行搜索 - 只需要进行直接索引操作。

对于直接索引查找，数组基本上是理想的 - 这只是一个简单的情况。

pointer_into_array = base_pointer + offset * size

（随后是指针解引用。）

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

像往常一样，选择适合工作的数据结构-如果你真的可以只索引数组(或List<T>)，那么这将非常快。