为什么hashset.except迭代和检查的速度是其他集合的两倍？

Question

我只是做了一些优化,对此感到困惑.

我的原始代码看起来像这样:

   HashSet<IExampleAble> alreadyProcessed;//a few million items
    void someSetRoutineSlower(HashSet<IExampleAble> exampleSet)
    {

        foreach (var item in exampleSet)
        {
            if (!alreadyProcessed.Contains(item))
            {
                // do Stuff
            }
        }
    }

这需要大约120万个滴答来处理.

然后我尝试了同样的事情,除了:

 void someSetRoutineFaster(HashSet<IExampleAble> exampleSet)
    {
        exampleSet.ExceptWith(alreadyProcessed);//doesnt this have to check each item of it's collection against the other one, thus actually looping twice?
        foreach (var item in exampleSet)
        {
            // do Stuff
        }
    }

它以约0.4mil-0.7mil的速度运行.

除了？之外,正在进行什么样的优化？它不是像我在第一个代码片段中那样检查所有项目吗？

Answer 1

根据参考源， .NET Framework 4.7.2 中的HashSet exceptWith 方法如下所示：

public void ExceptWith(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other");
        }
        Contract.EndContractBlock();

        // this is already the enpty set; return
        if (m_count == 0) {
            return;
        }

        // special case if other is this; a set minus itself is the empty set
        if (other == this) {
            Clear();
            return;
        }

        // remove every element in other from this
        foreach (T element in other) {
            Remove(element);
        }
    }

该方法中的显式优化仅适用于集合为空或自身“例外”时的特殊情况。

当 Contains(T) 调用的数量与集合大小相当时，您遇到的速度可能来自调用 Contains(T) 和迭代所有元素之间的差异。从表面上看，它似乎应该显式地执行相同的称为 Contains(T) 的旧实现，新实现在 Remove(T) 中执行相同类型的搜索。不同之处在于，随着元素被删除，集合的内部结构变得更加稀疏。这会导致每个存储桶的统计数据较少（根据源代码符号表示的插槽），并且查找元素变得更快，如果存在，则它是存储桶中的第一个项目。

这完全取决于对象的哈希函数的质量。理想情况下，每个对象都应该单独存在于其存储桶中，但大多数实际的哈希函数会分配数百万个存在冲突的元素（同一存储桶中的多个元素）。