是可枚举的.ElementAt<TSource>O(1) 对于 HashSet? [英] Is Enumerable.ElementAt<TSource> O(1) for HashSet?
问题描述
HashSet.ElementAt 中的实现是 O(1)，如果不是，它是什么?
Is the implementation in HashSet.ElementAt O(1) and if not, what is it?
推荐答案
不，它是 O(n).IEnumerable 上的所有扩展方法都必须是 O(n)(因为 IEnumerable 唯一能做的就是......枚举).虽然，正如评论中所指出的，他们确实尝试转换为可以更快地实现操作的接口(例如，ElementAt 将尝试转换为 IList> 以实现 O(1) 操作).对于 HashSet<T> 来说，这并没有帮助，它无论如何都没有实现 IList<T>.
No, it's O(n). All of the extension methods on IEnumerable<T> are, by necessity O(n) (because the only thing that IEnumerable<T> can do is ... enumerate). Although, as pointed out in the comments, they do attempt to cast to an interface that can implement the operation faster (for example, ElementAt will try to cast to IList<T> in order to implement an O(1) operation). Not that that helps in the case of HashSet<T> which doesn't implement IList<T> anyway.
对于 HashSet<T> 无论如何，ElementAt"的概念并没有真正的意义，因为没有这样的排序".你基本上只是得到一个随机元素.
For HashSet<T> the concept of "ElementAt" doesn't really make sense anyway, because there is no "ordering" as such. You're basically just getting a random element.
这篇关于是可枚举的.ElementAt<TSource>O(1) 对于 HashSet?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
