.net - 是 Enumerable.ElementAtHashSet 的 O(1)？

Question

是HashSet.ElementAtO(1) 中的实现吗？如果不是，它是什么？

Answer 1

不，它是 O(n)。所有的扩展方法IEnumerable<T>都必然是 O(n) （因为唯一IEnumerable<T>能做的就是......枚举）。尽管正如评论中所指出的，他们确实尝试转换为可以更快地实现操作的接口（例如，ElementAt将尝试转换为IList<T>以实现 O(1) 操作）。并不是说在HashSet<T>不实施的情况下有帮助IList<T>。

因为HashSet<T>“ElementAt”的概念无论如何都没有真正的意义，因为没有这样的“排序”。你基本上只是得到一个随机元素。

Answer 2

这取决于下分类列表类型。反射器显示Enumerable<T>.ElementAt(...)试图投射到IList<T>第一个。在这种情况下，它将是 O(1)。

例如，查询提供程序可能会返回一个IList<T>. 但很有可能，如果你应用任何 Linq 运算符，它都会变成IEnumerable<T>，因为它们只是使用不同的枚举器构建的，它会变成 O(n)。

编辑：我重读了HashSet. AHashSet<T>没有实现IList<T>，因此它是 O(n)。

Answer 3

中没有ElementAt方法，HashSet因此您可能想知道该Enumerable.ElementAt方法在HashSet<T>.

该Enumerable.ElementAt方法对实现的类型进行了优化IList<T>。在这种情况下，性能是 O(1)。但是 HashSet 没有实现这个接口，所以性能是 O(n)。