c# - 为什么hashset.exceptwith包含另一个集合的迭代和检查速度快两倍？

我只是做了一些优化，对此感到困惑。

我的原始代码如下所示:

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

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

这大约需要120万个滴答声。

然后我尝试了与exceptwith相同:

 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
        }
    }

它的运行速度大约为40万至70万滴答。

除了进行什么优化？就像我在第一个代码片段中所做的那样，它还不必检查所有项目吗？

最佳答案

根据.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)调用的数量与设置的大小相当时，调用所包含的(T)和遍历所有元素之间的差异可能会加快您的体验。从表面上看，它似乎应该显式执行相同的旧实现，即Contains(T)，而新实现则在Remove(T)中执行相同的搜索。不同之处在于，随着元素被删除，集合的内部结构变得更加稀疏。这样可以在统计上使每个存储桶中的项目减少(按源代码表示法分配插槽)，并且发现一个元素变得更快(如果存在)，则它是存储桶中的第一项。

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