代码之家 › 专栏 › 技术社区 › Rotsor

为什么dictionary.first()这么慢?

hashtable algorithm performance .net

8

Rotsor · 技术社区 · 15 年前

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

我一直认为,如果散列正确,散列表是最快的关联容器。

但是,下面的代码速度非常慢。它只执行大约100万次迭代,在核心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.

只需将字典更改为SortedDictionary即可获得:

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

速度快300倍,迭代次数少2倍。

同样的情况也发生在Java中。使用 HashMap 而不是 Dictionary 和 keySet().iterator().next() 而不是 Keys.First() .

5 回复 | 直到 14 年前

1

15

SLaks 14 年前

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

它的枚举器将遍历哈希表中的存储桶,直到找到一个非空的存储桶,然后返回该存储桶中的值。
一旦字典变大,这个操作就会变得昂贵。
此外,从字典中删除一个项不会收缩buckets数组,因此 First() 呼叫获取 更慢的 当你移除物品时。(因为它必须进一步循环才能找到一个非空的桶)

因此,反复呼叫 第一() 去除是O(N ^二 )

顺便说一下,您可以避免这样的值查找:(这不会使它明显更快)

var kvp = todo.First();

//Use kvp.Key and kcp.Value

2

4

Matthew Flaschen 15 年前

字典不努力跟踪关键字列表。所以迭代器需要遍历桶。这些桶中的许多,特别是对于一本大字典来说,其中许多没有任何内容。

比较OpenJDK可能会有所帮助 HashIterator.nextEntry 和 PrivateEntryIterator.nextEntry (使用treemap.successor)。哈希版本将遍历未知数量的条目,以查找非空的条目。如果散列表删除了许多元素(在您的例子中就是这样),那么这可能会特别慢。在Treemap中,我们唯一要做的就是按顺序遍历。路上没有空(只有叶子处)。

3

1

Meiscooldude 15 年前

好吧,哈希表没有排序,我猜它必须先做某种排序,然后才能进行迭代,或者进行某种扫描,如果已经排序了,它就可以循环通过。

4

1

Mark Brackett 15 年前

反射镜显示 Dictionary<TKey, TValue> 维护一个 Entry<TKey, TValue> 数组就是它的 KeyCollection<TKey, TValue>.Enumerator<TKey, TValue> 使用。通常,查找应该相对快速,因为它可以索引到数组中(假设您不希望 First ):

// Dictionary<TKey. TValue>
private Entry<TKey, TValue>[] entries;

然而 ,如果要删除该数组的第一个元素,则最终将遍历该数组,直到找到一个非空元素:

// Dictionary<TKey, TValue>.KeyCollection<TKey, TValue>.Enumerator<TKey, TValue>
while (this.index < this.dictionary.count) {
    if (this.dictionary.entries[this.index].hashCode >= 0) {
        this.currentKey = this.dictionary.entries[this.index].key;
        this.index++;
        return true;
    }
    this.index++;
}

当您删除条目时,您开始在 entries 数组,检索速度变慢 弗斯特 下一次。

5

0

Amadan 15 年前

不进行查找,排序字典的最简单实现是键的排序列表(如treeset)和哈希组合;列表为您提供排序,字典为您提供值。因此,按键已经可用。哈希表没有随时可用的键,因此罪犯不是 first 它是 keys (没有任何证据,可以自由地检验假设;d)