为什么HashSet 类不用于实现Enumerable.Distinct
我需要以大O表示法访问IEnumerable.Distinct
的渐近时间和空间复杂度
所以我在看扩展方法Enumerable.Distinct
的实现,我看到它是使用和内部类Set
,这几乎是一个带有“开放寻址”的哈希表的经典实现
很快引起注意的是Set
中的很多代码只是来自HashSet
的复制粘贴,有一些遗漏
但是,这个简化的Set
实现有一些明显的缺陷,例如Resize
方法不使用素数作为槽的大小,比如HashSet
,看看HashHelpers.ExpandPrime
所以,我的问题是:
- 这里代码重复的原因是什么,为什么不坚持DRY原则? 特别是考虑到这两个类都在同一个程序集
System.Core
- 看起来
HashSet
会表现得更好,所以我应该避免使用Distinct扩展方法,并编写我自己的扩展方法,使用HashSet
而不是Set
?
这几乎是具有“开放寻址”的哈希表的经典实现
再看一遍。 它与列表头单元格分开链接。 虽然插槽都在一个arrays中,但在碰撞情况下找到下一个插槽是通过检查当前插槽的next
字段来完成的。 这比使用链接列表和每个节点作为单独的堆对象具有更好的缓存效率,但在这方面不如开放寻址那么好。 同时,它避免了一些开放式寻址效果不佳的情况。
Set中的很多代码只是来自HashSet的复制粘贴,有一些遗漏
AFAICT使用哈希集的私有实现的原因是Enumerable
和HashSet
几乎在同一时间独立开发。 这只是我的猜想,但它们都是用.NET 3.5引入的,所以它是可行的。
很可能HashSet
通过复制Set
,然后使其更好地服务于公开曝光,尽管这两者都可能都基于与列表头单元格分开链接的相同原则
在性能方面, HashSet
使用素数意味着它更有可能避免与较差的哈希冲突(但这只是一个优势,这不是一个简单的问题),但Set
在很多方面都较轻,特别是在.NET Core中删除了一些不需要的东西。 特别是,该版本的Set
利用了这样一个事实:一旦项目被删除(例如,在Intersect
期间发生),将永远不会添加任何项目,这允许它省去freelist
以及与之相关的任何工作, HashSet
无法做到的。 即使是最初的实施也没有跟踪版本以便在枚举期间捕获变化,这是一个很小的成本,但是每次添加和删除都是成本。
因此,对于具有不同哈希码分布的不同数据集,有时一个表现更好,有时另一个表现更好。
特别是考虑到这两个类都在同一个程序集System.Core中
仅在某些版本的.NET中,在某些版本中,它们位于不同的程序集中。 在.NET Core中,我们有两个版本的Set
,一个在具有System.Linq
的程序Set
,另一个在具有System.Linq
的单独程序集中。 前者如上所述被削减,后者替换为使用HashSet
因为它在那里做得少。
当然System.Core是第一位的,但是这些元素可以完全分开的事实说明System.Core不是一个单一依赖关系的整体blob。
现在在.NET Core的Linq版本中有一个ToHashSet()
方法,可以用HashSet
替换Set
HashSet
更合理,尽管不是一件容易的事。 我认为@james-ko正在考虑测试这样做的好处。
看起来
HashSet
会表现得更好
由于上面解释的原因,情况可能并非如此,但可能确实如此,具体取决于源数据。 这是在考虑经过一些不同的linq方法的优化之前(在linq的初始版本中并不多,但在.NET Core中很少)。
所以我应该避免使用
Distinct
扩展方法,并编写我自己的扩展方法,它将使用HashSet
而不是Set
。
使用Distinct()
。 如果你有一个瓶颈,那么HashSet
可能会在给定的数据集中获胜,但如果你这样做,请确保你的分析与你的代码在现实生活中会遇到的实际值非常接近。 没有必要决定一种方法是基于某些任意测试更快,如果你的应用程序遇到另一个做得更好的情况。 (如果我发现这是一个问题点,我会先看看有问题类型的GetHashCode()
是否可以针对速度或位分布进行改进,首先)。
上述就是C#学习教程:为什么HashSet 类不用于实现Enumerable.Distinct分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/988092.html