Является ли <Collection>.Count дорогим в использовании?

Question

Я пишу метод кеширования, который по сути выглядит следующим образом:

while ( myHashSet.Count > MAX_ALLOWED_CACHE_MEMBERS )
{
    EjectOldestItem( myHashSet );
}

Мой вопрос о том, как определяется Count: это просто private или protected int, или он рассчитывается путем подсчета элементов каждый раз, когда его вызывают?

Answer 1

С http://msdn.microsoft.com/en-us/library/ms132433.aspx:

Получение значения этого свойства является операцией O (1).

Это гарантирует, что доступ к Count не будет повторяться по всей коллекции.

---

Редактировать: как и предполагалось многими другими авторами, IEnumerable<...>.Count(), тем не менее, не гарантированно будет O (1). Используйте с осторожностью!

IEnumerable<...>.Count() - это метод расширения, определенный в System.Linq.Enumerable. Текущая реализация делает явный тест, если подсчитанный IEnumerable<T> действительно является экземпляром ICollection<T>, и использует ICollection<T>.Count, если это возможно. В противном случае он пересекает IEnumerable<T> (возможно, расширение ленивых вычислений расширяется) и считает элементы один за другим.

Однако я не нашел в документации, гарантируется ли, что IEnumerable<...>.Count() использует O (1), если это возможно, я только проверял реализацию в .NET 3.5 с Reflector.

---

Необходимое позднее добавление: многие популярные контейнеры не являются производными от Collection<T>, но, тем не менее, их свойство Count имеет значение O (1) (то есть не будет перебирать всю коллекцию). Примеры: HashSet<T>.Count (наиболее вероятно, о чем хотел спросить ОП), Dictionary<K, V>.Count, LinkedList<T>.Count, List<T>.Count, Queue<T>.Count, Stack<T>.Count и т. Д.

Все эти коллекции реализуют ICollection<T> или просто ICollection, поэтому их Count является реализацией ICollection<T>.Count (или ICollection.Count). Необязательно, чтобы реализация ICollection<T>.Count была операцией O (1), но упомянутые выше делают именно так, согласно документации.

(Обратите внимание: некоторые контейнеры, например Queue<T>, реализуют неуниверсальный ICollection, но не ICollection<T>, поэтому они "наследуют" свойство Count только от from ICollection.)

Answer 2

В вашем вопросе не указан определенный класс коллекции, так что ...

Это зависит от класса Коллекции. ArrayList имеет внутреннюю переменную, которая отслеживает количество, как и List. Однако это зависит от реализации, и в зависимости от типа коллекции теоретически может пересчитываться при каждом вызове.

Answer 3

Это внутреннее значение и не рассчитывается. Документация гласит, что получение значения является операцией O (1).

Answer 4

Как уже отмечали другие, счет сохраняется при изменении коллекции. Это почти всегда имеет место с каждым типом коллекции в рамках. Это значительно отличается от использования метода расширения Count в IEnumerable, который будет каждый раз перечислять коллекцию.

Кроме того, в более новых классах коллекций свойство Count не является виртуальным, что означает, что джиттер может встроить вызов средства доступа Count, что делает его практически таким же, как доступ к полю. Другими словами, очень быстро.

Answer 5

В случае HashSet это просто внутреннее поле int, и даже SortedSet (набор на основе двоичного дерева для .net 4) имеет счет во внутреннем поле.

Answer 6

Согласно Reflector, он реализован как

public int Count{ get; }

, поэтому он определяется производным типом

Answer 7

Просто короткая заметка. Имейте в виду, что существует два способа подсчета коллекции в .NET 3.5 при использовании System.Linq. Для обычной коллекции первым выбором должно быть использование свойства Count по причинам, уже описанным в других ответах.

Также доступен альтернативный метод через метод расширения LINQ .Count (). Интересной особенностью .Count () является то, что он может вызываться для ЛЮБОГО перечислимого независимо от того, реализует ли базовый класс ICollection или нет, или имеет ли он свойство Count. Однако если вы когда-нибудь вызовете .Count (), имейте в виду, что он будет перебирать коллекцию для динамической генерации счетчика. Это обычно приводит к сложности O (n).

Единственная причина, по которой я хотел это отметить, заключается в том, что, используя IntelliSense, часто легко случайно получить расширение Count (), а не свойство Count.

Answer 8

Это внутренний int, который увеличивается каждый раз, когда в коллекцию добавляется новый элемент.