23 votes

Est <Collection>.Le comte Cher à Utiliser?

Je suis en train d'écrire un cache-méthode d'éjection qui, pour l'essentiel ressemble à ceci:

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

Ma question est au sujet de la façon dont Count est déterminé: est-il juste un private ou protected int, ou est-il calculé en comptant les éléments à chaque fois son nom?

47voto

Vlad Points 23480

À partir de http://msdn.microsoft.com/en-us/library/ms132433.aspx:

Récupération de la valeur de cette propriété est un O(1) de l'opération.

Cela garantit que l'accès à l' Count de ne pas effectuer une itération sur l'ensemble de la collection.


Edit: comme beaucoup d'autres affiches suggéré, IEnumerable<...>.Count() est toutefois pas garanti à O(1). À utiliser avec précaution!

IEnumerable<...>.Count() est une extension de la méthode définie en System.Linq.Enumerable. L'implémentation actuelle fait un test explicite si l'compté IEnumerable<T> est en effet une instance d' ICollection<T>, et rend l'utilisation de l' ICollection<T>.Count si possible. Sinon, il traverse l' IEnumerable<T> (possible que l'évaluation différée développez) et compte les éléments un par un.

Je n'ai cependant pas trouvé dans la documentation qu'il est garanti qu' IEnumerable<...>.Count() utilise O(1) si possible, j'ai seulement vérifié la mise en œuvre dans .NET 3.5 avec Réflecteur.


Nécessaire ajout tardif: de nombreux populaire, les conteneurs ne sont pas dérivées d' Collection<T>, mais néanmoins leurs Count propriété est O(1) (qui est, de ne pas effectuer une itération sur l'ensemble de la collection). Des exemples sont HashSet<T>.Count (ce qui est le plus probable que l'OP voulais vous demander à propos de), Dictionary<K, V>.Count, LinkedList<T>.Count, List<T>.Count, Queue<T>.Count, Stack<T>.Count et ainsi de suite.

Toutes ces collections, mettre en oeuvre ICollection<T> ou juste ICollection, de sorte que leur Count est une implémentation de l' ICollection<T>.Count (ou ICollection.Count). Il n'est pas nécessaire pour une mise en œuvre de l' ICollection<T>.Count être un O(1) le fonctionnement, mais celles mentionnées ci-dessus font que, selon la documentation.

(Note de côté: certains des conteneurs, par exemple, Queue<T>, de mettre en œuvre non générique ICollection mais pas ICollection<T>, de sorte qu'ils "héritent" de la Count de la propriété uniquement à partir de ICollection.)

9voto

Nick Points 4676

Votre question n'est pas de spécifier un spécifique de la classe de Collection, donc...

Cela dépend de la classe de Collection. ArrayList est une variable interne qui permet de suivre le comte, comme le fait de Liste. Cependant, il est la mise en œuvre spécifique, et selon le type de la collection, il pourrait théoriquement obtenir recalculé à chaque appel.

7voto

AxelEckenberger Points 9546

C'est une valeur interne, et n'est pas calculée. La documentation stipule que l'obtention de la valeur est un O(1) de l'opération.

6voto

Josh Points 38617

Comme d'autres l'ont noté, le Comte est maintenu lors de la modification de la collecte. C'est presque toujours le cas avec chaque type de collection dans le cadre. Ce qui est considérablement différent que d'utiliser le Comte de la méthode d'extension sur un IEnumerable qui va énumérer la collection à chaque fois.

Aussi, avec la nouvelle collection de classes de la propriété Count n'est pas virtuel, ce qui signifie que la gigue peut inline l'appel au Comte d'accesseur qui fait qu'il est pratiquement le même que l'accès à un champ. En d'autres termes, très rapide.

4voto

Pent Ploompuu Points 4120

Dans le cas d'un HashSet c'est juste un interne int sur le terrain et encore SortedSet (un arbre binaire en fonction définie pour .net 4) a un nombre dans un champ interne.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X