¿Es Enumerable.ElementAt <TSource> O (1) para HashSet?

Question

Es la implementación en HashSet.ElementAt O (1) y si no es así, ¿qué es?

Answer 1

No, es O (n). Todos los métodos de extensión en IEnumerable<T> son, por necesidad, O (n) (porque lo único que puede hacer IEnumerable<T> es ... enumerar). Aunque, como se señala en los comentarios, intentan enviar a una interfaz que puede implementar la operación más rápido (por ejemplo, ElementAt intentará convertir a IList<T> para implementar una operación O (1)). No es que eso ayude en el caso de HashSet<T> que no implementa IList<T> de todos modos.

Para HashSet<T> el concepto de "ElementAt" no tiene mucho sentido de todos modos, porque no hay una "orden" como tal. Básicamente, estás obteniendo un elemento aleatorio.

Answer 2

No hay método en el ElementAtHashSet por lo que probablemente quieren saber el rendimiento del método Enumerable.ElementAt cuando se usa en una instancia de HashSet<T>.

El método Enumerable.ElementAt tiene una optimización para los tipos que implementan IList<T>. En ese caso, el rendimiento es O (1). Sin embargo, HashSet no implementa esta interfaz, por lo tanto, el rendimiento es O (n).

Answer 3

Depende del tipo de lista de subllantas. El reflector muestra que Enumerable<T>.ElementAt(...) intenta convertir primero a IList<T>. En ese caso sería O (1).

Un proveedor de consultas, por ejemplo, puede devolver algo que es un IList<T>. Pero lo más probable es que si aplica cualquiera de los operadores de Linq, se convertirá en IEnumerable<T>, ya que se construyen simplemente utilizando diferentes enumeradores, y se convertirá en O (n).

EDITAR: He leído el HashSet. Un HashSet<T> no implementa IList<T>, por lo tanto, es O (n).