为什么Dictionary.First（）这么慢？

  • Z时代
  • 2024-01-10
  • 分类：问答

这不是一个真正的问题，因为我已经找到了答案，但仍然很有趣。

我一直认为，如果正确地进行哈希处理，哈希表是最快的关联容器。

但是，以下代码非常慢。在Core 2 CPU上，它仅执行大约一百万次迭代，并花费超过2分钟的时间。

该代码执行以下操作：它维护todo需要处理的项目的集合。在每次迭代时，它都会从该集合中获取一个项目（与哪个项目无关），将其删除，如果未处理则对其进行处理（可能要添加更多的项目进行处理），然后重复此操作直到没有要处理的项目为止。

罪魁祸首似乎是Dictionary.Keys.First（）操作。

问题是为什么它速度慢？

Stopwatch watch = new Stopwatch();
watch.Start();
HashSet<int> processed = new HashSet<int>();
Dictionary<int, int> todo = new Dictionary<int, int>();
todo.Add(1, 1);
int iterations = 0;
int limit = 500000;
while (todo.Count > 0)
{
    iterations++;
    var key = todo.Keys.First();
    var value = todo[key];
    todo.Remove(key);
    if (!processed.Contains(key))
    {
        processed.Add(key);
        // process item here
        if (key < limit) { todo[key + 13] = value + 1; todo[key + 7] = value + 1; }
        // doesn't matter much how
    }
}
Console.WriteLine("Iterations: {0}; Time: {1}.", iterations, watch.Elapsed);

结果是：

Iterations: 923007; Time: 00:02:09.8414388.

只需将Dictionary更改为SortedDictionary即可：

Iterations: 499976; Time: 00:00:00.4451514.

快了300倍，而迭代次数却减少了2倍。

在Java中也是如此。用于HashMap代替Dictionary和keySet().iterator().next()代替Keys.First()。

回答：

Dictionary<TKey, TValue> 维护哈希表。

它的枚举器将遍历哈希表中的存储桶，直到找到一个非空存储桶，然后返回该存储桶中的值。

一旦字典变大，此操作将变得很昂贵。

此外，从字典中删除项目不会缩小buckets数组，因此在删除项目时First()调用会 变慢 。（因为必须进一步循环才能找到非空存储桶）

因此，重复调用First()和删除是O（n 2）。

顺便说一句，您可以避免像这样进行值查找：（这不会使其明显变快）

var kvp = todo.First();
//Use kvp.Key and kcp.Value

以上是 为什么Dictionary.First（）这么慢？ 的全部内容， 来源链接： utcz.com/qa/410035.html

回到顶部