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

StackOverflow https://stackoverflow.com/questions/908050

  •  05-09-2019
  •  | 
  •  

题

我正在写一个7张牌作为评价者我的宠物项目之一。虽然试图优化其速度（我喜欢的挑战），我震惊地发现，相对于阵列的索引查找字典键查找的性能是相当缓慢的。

例如，我跑，列举52在所有选择7 = 133784560可能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）查找，所以我期望阵列查找要快，但不受此多！

我目前存储在字典扑克手牌排名。我想，如果这是快如字典查找就可以了，我不得不重新考虑我的方法和使用数组来代替，虽然索引的排名会得到一个有点棘手，我可能要问一下另一个问题。

有帮助吗？

解决方案

不要忘了大O表示法只是说复杂是如何增长的相对大小（ETC） - 它不给所涉及的持续性因素的任何迹象。这就是为什么有时甚至是线性的搜索的钥匙比字典查找更快，当有足够几个键。在这种情况下，你甚至没有做与阵列搜索虽然 - 只是一个单纯的索引操作

。

有关直索引查找，阵列是基本上理想的 - 它只是的情况

pointer_into_array = base_pointer + offset * size

（然后一个指针引用。）

执行字典查找相对复杂 - 非常快（比方说）通过键的线性查找时有很多键，但比直阵列查找复杂得多比较。它来计算密钥的散列，然后制定出其桶，应该在，可能处理重复散列（或重复的桶），然后检查是否相等。

像往常一样，为任务选择合适的数据结构 - 如果你真的可以只用索引到一个数组（或List<T>），然后是跑不掉，那将是令人眼花缭乱的快速

其他提示

  

时这种类型的行为预期（由8倍的性能降低）？

为什么呢？每个阵列查找几乎intantaneous /可忽略，而词典查找可能需要至少一个额外的子程序调用。

它们两者为O的点（1）意味着，即使你有每一组中的50倍以上的项时，性能降低仍然只是一个因素不管它是（8）

东西可以采取千年，并且仍然是O（1）。

如果您通过这个代码的反汇编窗口单步，你会很快明白过来的区别是什么。

当密钥空间非常大，并且不能被映射到一个稳定的

词典结构是最有用的，测序顺序。如果可以将键转换成一个简单的整数在相对小的范围内，你将很难再找到的数据结构将不是一个数组更好的表现。

在一个实施音符;在.NET中，字典是基本hashables。您可以一定程度上改善确保您的关键字散列成唯一值的大空间中的关键查找性能。它看起来像你的情况，您使用的是简单的整数作为键（我相信散列到其自身的价值） - 这样就可能是你能做的最好的

这是数组的查找是你可以做的跑得最快的家伙 - 基本上所有它是指针运算的单位从阵列到你想找到的元素开始走。在另一方面，字典查找很可能是有点慢，因为它需要做的散列和关注本身找到正确的桶。虽然预期运行时也是O（1） - 算法的常数更大所以这将是慢

。

欢迎到大O符号。你总是要考虑到这牵涉到常数因子。

做一个字典-查找当然是更昂贵的比阵列查找。

大O只告诉你如何算法尺度。查找一倍的量，看看数字如何变化：双方应采取绕两次时间

从词典检索的元件的成本是O（1），但那是因为一本字典是一个哈希表来实现 - 所以你必须先计算散列值就知道要返回的元素。哈希表往往不是有效的 - 但他们是很好的大型数据集，或者说有很多独特的散列值的数据集

。

在列表（除了是用于dercribe阵列而不是一个链表垃圾字！）将更快，因为它会通过直接计算想要返回的元件返回的值。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top