为什么是哈希集.除了以两倍的速度迭代和检查另一个集合上的包含
本文关键字:迭代 速度 检查 另一个 包含 集合 两倍 哈希集 为什么 | 更新日期: 2023-09-27 18:17:20
我刚刚做了一些优化,却被这个问题搞糊涂了。
我的原始代码看起来像这样:
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
}
}
以0.4 -0.7mil的节拍运行
exceptwith中正在进行什么样的优化?它不也必须像我在第一个代码片段中所做的那样检查所有项目吗?
根据。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);
}
}
方法中的显式优化只适用于set为空或与自身"例外"的特殊情况。
您所经历的速度可能来自调用Contains(T)和遍历所有元素之间的差异,当调用Contains(T)的次数与集合大小相当时。从表面上看,它似乎应该显式地执行称为Contains(T)的旧实现,新实现在Remove(T)中执行相同类型的搜索。不同之处在于,当元素从集合中移除时,它的内部结构变得更加稀疏。这导致统计上每个桶的条目(每个源代码符号的插槽)更少,并且查找元素变得更快,如果存在,则它是桶中的第一项。
这完全取决于对象的哈希函数的质量。理想情况下,每个对象都应该单独在它的桶中,但大多数实际的哈希函数会分布上百万个有碰撞的元素(多个元素在同一个桶中)。