c# – 为什么没有IOrderedEnumerable重新实现.Contains()来获得
|
如果你去这里：
The IOrderedEnumerableDocs然后点击.Contains()方法然后它会带你到这里：
the generalised Enumerable.Contains() docs
我认为这意味着它只是使用底层的IEnumerable实现？ 考虑到你知道你有一个可以与你的元素进行比较的排序列表(例如,进行二元搜索以确认元素是否存在,而不是枚举整个集合),这似乎很奇怪,因为有可能进行更高效的搜索. 我错过了什么吗？ 解决方法
从一开始就值得注意的是,给定方法仅被记录为在IEnumerable< T>上运行的事实.并不意味着它没有针对给定的实现或派生接口进行优化.事实上,Enumerable中的许多方法为不同的派生接口和/或具体实现采用不同的路径.这里的经典示例是,如果IEnumerable< T>,则Count()采用不同的路径.在工具ICollection< T>上调用它或ICollection.在完整框架中还有几个这样的例子,在.NET Core中甚至更多,包括一些采用优化路径来实现IOrderedEnumerable< T>.你从调用OrderBy()得到.
其中一些是我做的,因为我的爱好这些日子对.NET Core有贡献,特别是对Linq,特别是性能改进(尽管很明显,如果我正在攻击某些东西,我需要增加对我触摸的位的测试,当这样做时会出现小错误,他们会优先考虑性能改进). 说到IOrderedEnumerable,我做过像改变.OrderBy(someLambda).Skip(j).从O(n log n)时间到(k)(公共分页习语)计算和O(jk)时间到枚举到O(nk log k)计算时间和O(k)枚举时间,和.OrderBy(someLambda).O(n)空间的第一个()和O(1)空间的O(n log n)时间和O(n)时间,等等. 我可能会考虑改进其他方法,当然如果我不这样做,很可能别人会这样做. 如果我这样做,我不会按照你的建议去做. 首先,为IOrderedEnumerable< T>提供单独的重载.将需要向公共API添加方法但仅涵盖一些情况(可能我们作为IEnumerable< T>给出的实际上是IOrderedEnumerable< T>).为IEnumerable< T>设置过载要好得多.并检测IOrderedEnumerable< T>案件. 其次要使用二进制搜索,我们必须知道IOrderedEnumerable的排序方式.使用OrderedEnumerable< TElement,TKey>这是可能的.通过调用OrderBy创建,但不是更普遍. 第三,它不会是最大的收获. source.OrderBy(someLambda).Contains(someItem)的当前成本如下： >缓冲源：O(n)空间,O(n)时间. 如果Contains()被优化为使用二进制搜索,它将变为： >缓冲源：O(n)空间,或者确认不存在：O(log n)时间(平均值,O(n)更差,因为精确匹配可能与所有元素排序在同一级别,并且必须与所有元素进行比较他们). 然而,这完全是浪费.如果我们想要优化Contains()(以及许多其他聚合方法),那么最佳策略是： >调用source.Contains(someItem)并返回结果.这将更糟糕的是O(n)时间和O(1)空间,但是如果源是例如HashSet< T>,则它可以是O(log n)或O(1)时间. (Contains()的情况已经优化).在理论和实践中,它最终将比上面的缓冲步骤更快. 实施这一改变将大大减少工作量,并获得更大的收益. 我考虑过这个问题,并且可能确实提交了这样一个公关,但我还不确定它是否值得(因此,如果其他人提交这样的公关,我的意见是什么),因为它几乎总是更容易调用者转向… .OrderBy(foo).包含(bar)到.Contains(bar)本身,优化这种情况所需的检查将是便宜的,但不是完全免费的. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |