小编典典

为什么Dictionary.First()这么慢?

algorithm

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

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

但是,以下代码非常慢。在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代替DictionarykeySet().iterator().next()代替Keys.First()


阅读 480

收藏
2020-07-28

共1个答案

小编典典

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

它的枚举器将遍历哈希表中的存储桶,直到找到一个非空存储桶,然后返回该存储桶中的值。
一旦字典变大,此操作将变得很昂贵。
此外,从字典中删除项目不会缩小buckets数组,因此在删除项目时First()调用会 变慢 。(因为必须进一步循环才能找到非空存储桶)

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


顺便说一句,您可以避免像这样进行值查找:(这不会使其明显变快)

var kvp = todo.First();

//Use kvp.Key and kcp.Value
2020-07-28