Является счетным. ElementAt <TSource> O (1) для HashSet?
Реализация в HashSet.ElementAt O (1) и в противном случае что это?
3 ответа
Нет, это O (n). Все методы расширения в IEnumerable по необходимости имеют O (n) (потому что единственное, что может сделать IEnumerable , - это ... перечислить). Хотя, как указано в комментариях, они все же пытаются выполнить приведение к интерфейсу, который может реализовать операцию быстрее (например, ElementAt попытается привести к IList в чтобы реализовать операцию O (1)). Не то чтобы это помогло в случае HashSet , который в любом случае не реализует IList .
Для HashSet концепция «ElementAt» в любом случае не имеет смысла, потому что нет «упорядочивания» как такового. По сути, вы просто получаете случайный элемент.
Зависит от типа списка подчиненных. Отражатель показывает, что Enumerable сначала пытается привести к IList . В этом случае это будет O (1).
Поставщик запроса, например, может вернуть что-то, что является IList . Но есть вероятность, что если вы примените любой из операторов Linq, он превратится в IEnumerable , потому что они построены просто с использованием разных счетчиков, и он станет O (n).
РЕДАКТИРОВАТЬ: Я перечитал HashSet . A HashSet не реализует IList , поэтому это O (n).
В HashSet нет метода ElementAt , поэтому вы, вероятно, захотите узнать производительность Enumerable.ElementAt ] при использовании в экземпляре HashSet .
Метод Enumerable.ElementAt имеет оптимизацию для типов, реализующих IList . В этом случае производительность будет O (1). Однако HashSet не реализует этот интерфейс, поэтому производительность равна O (n).