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

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 万个滴答来处理。

然后我用 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 万次。

exceptwith 进行了什么样的优化？它是否也必须像我在第一个代码片段中所做的那样检查所有项目？

Answer 1

根据 HashSet 的引用来源.NET Framework 4.7.2 中的 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);
        }
    }

该方法中只有显式优化适用于集合为空或自身“异常(exception)”的特殊情况。

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

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