Является ли Enumerable.ElementAt <TSource>O (1) для HashSet?

Question

Является ли реализация в HashSet.ElementAt O (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

Это зависит от типа списка underyling. Отражатель показывает, что Enumerable<T>.ElementAt(...) сначала пытается привести к IList<T>. В этом случае это будет O (1).

Поставщик запросов, например, может вернуть что-то, что IList<T>. Но есть вероятность, что если вы примените какой-либо из операторов Linq, он превратится в IEnumerable<T>, потому что они построены просто с использованием различных перечислителей, и он станет O (n).

РЕДАКТИРОВАТЬ: я перечитал HashSet. A HashSet<T> не реализует IList<T>, поэтому это O (n).

Answer 3

В HashSet нет метода ElementAt, поэтому вы, вероятно, хотите узнать производительность метода Enumerable.ElementAt при его использовании в экземпляре HashSet<T>.

Метод Enumerable.ElementAt имеет оптимизацию для типов, реализующих IList<T>. В этом случае производительность O (1). Однако HashSet не реализует этот интерфейс, поэтому производительность равна O (n).