Les collections en .NET

Cet article a pour objectif de présenter les principales collections présentes dans le framework .NET et leurs avantages et inconvénients, principalement en terme de complexité algorithmique. Ensuite, je ferai une petite introduction à LINQ. Enfin, vous trouverez le code C# pour une classe nommée LazyList<T>, qui profite des avantages d’une énumération LINQ et de ceux d’une List<T>.

Descriptions des principales collections

Array

  • Ecriture
    • Ajout / Suppression : Non
    • Modification : Oui
    • Thread safe : Non
  • Complexité
    • Accès par indice : O(1)
    • Recherche : O(n)

Il s’agit de la collection de base, avec accès par indice. C’est également la moins gourmande en mémoire et la plus rapide d’accès.

C’est un des choix les plus évidents pour gérer une collection de taille fixe.

 

List<T>

  • Ecriture
    • Ajout / Suppression : Oui
    • Modification : Oui
    • Thread safe : Non
  • Complexité
    • Accès par indice : O(1)
    • Ajout : O(1) sauf cas particulier
    • Recherche : O(n)
    • Suppression : O(n)
    • Insertion à un indice : O(n)

La liste est une collection avec accès par indice très polyvalente, et performante pour la lecture et l’ajout.

Elle utilise un tableau interne, qui commence avec une taille de 4, qui double à chaque fois qu’on dépasse la capacité. Dans ce cas (5ème, 9ème, 17ème élément…), l’ajout a une complexité de O(n). L’utilisation mémoire est donc similaire à celle d’un tableau dans le meilleur des cas, presque deux fois moins bonne dans le pire des cas.

C’est un très bon choix lorsque vous ajoutez un nombre inconnu d’éléments à une collection.

 

Stack<T>, Queue<T>

  • Ecriture
    • Ajout / Suppression : Oui
    • Modification : Non
    • Thread safe : Non
  • Complexité
    • Accès au dernier (Stack) ou premier (Queue) élément : O(1)
    • Ajout : O(1) sauf cas particulier
    • Recherche : O(n)
    • Suppression du dernier (Stack) ou premier (Queue) élément : O(1)

Stack (pile) représente une collection de type LIFO (Last in, first out). Queue (file) représente une collection de type FIFO (First in, first out). Ces deux collections sont limitées à l’ajout et au retrait du premier ou dernier élément, mais ces deux opérations sont très performantes.

 

Dictionary<TKey, TValue>

  • Ecriture
    • Ajout / Suppression : Oui
    • Modification : Oui
    • Thread safe : Non
  • Complexité
    • Accès à un élément par sa clé : O(1)
    • Ajout : O(1) sauf cas particulier
    • Suppression d’un élément par sa clé : O(1)

Le dictionnaire est la classe la plus pratique pour une collection clé/valeur. Attention cependant qu’une clé ne peut avoir qu’une seule valeur. Cette classe est assez performante, même sur les grosses collections.

Cependant, elle se base sur le hash code de la clé, donc faites en sorte qu’il soit rapide à calculer. Par exemple, utiliser un string de 2000 caractères comme clé est une très mauvaise idée. De même, si la clé est une structure perso, il est indispensable de surcharger GetHashCode() pour éviter d’utiliser de la réflexion.

Une chose à laquelle il faut faire attention : lorsqu’on parcourt un dictionnaire, il n’est pas garanti que les éléments soient dans l’ordre d’insertion.

 

HashSet<T>

  • Ecriture
    • Ajout / Suppression : Oui
    • Modification : Non
    • Thread safe : Non
  • Complexité
    • Ajout d’un élément : O(1) sauf cas particulier
    • Suppression d’un élément : O(1)
    • Recherche d’un élément : O(1)

Un hash set est une collection d’objets qui est là pour savoir si un objet se trouve dedans ou non, grâce à une recherche de complexité O(1).

Se basant sur le hash de l’objet, les précautions à prendre sont les mêmes que pour la clé du dictionnaire.

 

ObservableCollection<T>

  • Ecriture
    • Ajout / Suppression : Oui
    • Modification : Oui
    • Thread safe : Non
  • Complexité
    • Accès par indice : O(1)
    • Ajout : O(1) sauf cas particulier
    • Recherche : O(n)
    • Suppression : O(n)
    • Insertion à un indice : O(n)

Cette collection est quasi identique à une liste. La seule vraie différence est qu’elle expose l’événement CollectionChanged, déclenché dès que la collection est modifiée. Elle est particulièrement utilisée dans les ViewModels d’applications WPF / Windows Store / Silverlight.

 

ReadOnlyCollection<T>

  • Ecriture
    • Ajout / Suppression : Non
    • Modification : Non
  • Complexité
    • Accès par indice : O(1)
    • Recherche : O(n)

Cette collection est là pour ne pas être modifiable. Elle se base sur une collection implémentant IList<T>, telle qu’une liste ou un tableau. C’est utile si l’on veut fournir une collection sans pouvoir modifier la collection d’origine et sans dupliquer la collection.

 

LinkedList<T>

  • Ecriture
    • Ajout / Suppression : Oui
    • Modification : Non
    • Thread safe : Non
  • Complexité
    • Accès au premier ou dernier élément : O(1)
    • Recherche : O(n)
    • Ajout en début ou fin : O(1)
    • Insertion après ou avant un élément : O(1)
    • Suppression : O(1)

Cette classe représente une liste doublement chaînée. Il s’agit d’une collection relativement gourmande en mémoire (par exemple, sans même compter le stockage des objets eux-mêmes, il faut compter 32 octets par élément pour une application 64 bits). Cependant, toutes ses actions d’écriture sont de complexité O(1), et c’est la seule collection parmi celles décrites ici qui ne risque pas de se trouver dans le Large Object Heap.

 

ConcurrentStack<T>, ConcurrentQueue<T>, ConcurrentDictionary<TKey, TValue>

Ces trois classes sont identiques à leur équivalent non « concurrent », à la différence qu’elles sont thread safe.

 

BlockingCollection<T>

  • Ecriture
    • Ajout / Suppression : Oui
    • Modification : Non
    • Thread safe : Oui
  • Complexité
    • Accès au dernier (Stack) ou premier (Queue) élément : O(1)
    • Ajout : O(1) sauf cas particulier
    • Recherche : O(n)
    • Suppression du dernier (Stack) ou premier (Queue) élément : O(1)

Cette collection se base soit sur une ConcurrentQueue<T> (par défaut) soit sur une ConcurrentStack<T>. La différence est qu’elle permet d’imposer un nombre maximum d’éléments. Dans ce cas, l’ajout d’un élément devient bloquant au-delà de ce nombre.

Par exemple, une telle collection est pratique lorsqu’on veut faire un workflow avec plusieurs tâches en parallèle, mais en contrôlant le degré de parallélisme.

 

ConcurrentBag<T>

  • Ecriture
    • Ajout / Suppression : Oui
    • Modification : Non
    • Thread safe : Oui
  • Complexité
    • Accès à un élément : O(1)
    • Ajout : O(1)
    • Recherche : O(n)
    • Suppression : O(1)

Cette classe est une version thread safe de la LinkedList<T>.

Fonctionnalités Complexité
Ajout / Suppression Modification Thread safe Accès par indice / clé Recherche Ajout Suppression Insertion à un emplacement précis
Array Non Oui Non O(1) O(n)
List<T> Oui Oui Non O(1) O(n) O(1)* O(n) O(n)
Stack<T> Oui Non Non O(n) O(1)* O(1)
Queue<T> Oui Non Non O(n) O(1)* O(1)
Dictionary<TKey, TValue> Oui Oui Non O(1) O(n) O(1)* O(1)
HashSet<T> Oui Non Non O(1) O(1)* O(1)
ObservableCollection<T> Oui Oui Non O(1) O(n) O(1)* O(n) O(n)
ReadOnlyCollection<T> Non Non Non O(1) O(n)
LinkedList<T> Oui Non Non O(n) O(1) O(1) O(1)
ConcurrentStack<T> Oui Non Oui O(n) O(1)* O(1)
ConcurrentQueue<T> Oui Non Oui O(n) O(1)* O(1)
ConcurrentDictionary<TKey, TValue> Oui Oui Oui O(1) O(n) O(1)* O(1)
BlockingCollection<T> Oui Non Oui O(1) O(n) O(1)* O(1)
ConcurrentBag<T> Oui Non Oui O(1) O(n) O(1) O(1)

 

* : Lorsque la taille de la collection dépasse 2n éléments (à partir de 5), la collection est copiée dans un nouveau tableau deux fois plus grand. Cette copie est de complexité O(n).

 

LINQ (Language Integrated Query) et yield

Grande nouveauté du Framework 3.5, LINQ permet d’effectuer des requêtes sur les collections C#. Sa grande puissance est, entre autres, l’utilisation du mot-clé yield.

 

Le mot-clé yield

Celui-ci permet une énumération retardée (lazy) de la collection. De plus, seul le contexte de l’énumérateur est gardé en mémoire. Quand on appelle une méthode renvoyant un IEnumerable<T> qui utilise yield, on garde en mémoire le contexte d’appel. Ensuite, lorsque l’on cherche à énumérer cette collection (grâce à un foreach, par exemple), la méthode commence à s’exécuter, jusqu’au premier yield return xxxxxx (auquel cas, l’élément courant dans le foreach devient alors xxxxxx), yield break (auquel cas, le foreach considère qu’il n’y a plus d’élément dans la collection) ou jusqu’à la fin de la méthode (auquel cas, le foreach considère qu’il n’y a plus d’élément dans la collection). Une telle collection peut donc tout-à-fait ne pas avoir de fin (boule infinie).

Voici, par exemple, une méthode qui renvoie une énumération de tous les nombres pairs positifs :

Si l’on met un point d’arrêt dans le for, on se rend compte que l’on n’y rentre qu’à partir du moment où l’on énumère (par exemple dans un foreach) le retour de la méthode, et qu’on ne passe à l’itération suivante du for qu’au moment où l’on appelle MoveNext() (l’itération suivante du foreach).

Grâce à ça, le C# intègre un langage de requêtage très performant et extrêmement pratique : LINQ.

 

Présentation de LINQ et de la méthode Where()

L’une des choses les plus importantes lorsqu’on cherche à manipuler une collection, c’est de pouvoir la filtrer. Grâce à LINQ, c’est extrêmement facile à faire. Il existe deux syntaxes. La première est très proche du SQL :

La deuxième utilise des méthodes d’extension et des lambdas :

Personnellement, je préfère la deuxième, et me baserai donc exclusivement sur elle pour la suite.

On voit donc qu’il est extrêmement simple, grâce à LINQ, de filtrer sa collection. Notez cependant que la collection renvoyée est de type IEnumerable<T>. Cela est dû au fait que la méthode Where() tire parti du mot-clé yield. En effet, les lignes ci-dessus ne font rien de plus que déclarer une variable et lui fournir un contexte. Le filtre ne sera appliqué qu’au moment de l’énumération. De plus, tout le filtrage ne se fait pas d’un coup. Il se fait juste selon les besoins.

Quel intérêt ? Vous allez tout de suite comprendre avec la méthode First()

 

On énumère juste ce dont on a besoin : exemple avec First()

First() est une méthode qui lance l’énumération (à l’instar d’un foreach) mais arrête au premier élément. Si l’on reprend notre collection de nombres pairs, et qu’on veut le premier nombre pair différent de 0 qui soit divisible par 9, il suffit d’utiliser ce code :

Evidemment, on ne va pas s’amuser à regarder l’ensemble des nombres pairs pour trouver le premier qui soit divisible par 9. Et c’est là toute la puissance du mot-clé yield. L’appel à First() va itérer une seule fois sur la collection renvoyée par le Where() et pour chaque itération appelée sur le Where() (une seule dans notre cas), cette méthode va itérer jusqu’à ce que la condition soit vraie (donc uniquement les 10 premiers éléments : 0, 2, 4, 6, 8, 10, 12, 14, 16 et 18).

 

Les principales méthodes n’énumérant pas la collection

  • Distinct() : Renvoie les éléments de la collection sans doublons.
  • Except(otherCollection) : Renvoie les éléments se trouvant dans la collection source mais pas dans la collection en paramètre.
  • GroupBy(keySelector) : Regroupe les éléments de la collection selon leur clé.
  • Intersect(otherCollection) : Ne retourne que les éléments se trouvant dans les deux collections à la fois.
  • Join(otherCollection, keySelector, keySelector, resultSelector) : Effectue l’équivalent d’un INNER JOIN en SQL.
  • OfType<T>() : Filtre la collection en renvoyant uniquement les éléments du type en question. Le type des éléments de la collection renvoyée est changé pour correspondre au type choisis.
  • OrderBy(selector) / OrderByDescending(selector) / ThenBy(selector) / ThenByDescending() : Trie la collection.
  • Reverse : Renvoie la collection dans l’ordre inverse.
  • Select(resultSelector) : Effectue une transformation sur chaque élément de la collection.
  • SelectMany(resultCollectionSelector) : Aplatit une collection, c’est-à-dire transforme une collection de collections d’éléments en collection d’éléments.
  • Skip(number) : Renvoie une collection sautant les n premiers éléments de la collection source.
  • SkipWhile(condition) : Renvoie une collection sautant les premiers éléments de la collection source tant que la condition est vraie.
  • Take(number) : Renvoie une collection contenant au maximum les n premiers éléments de la collection source.
  • TakeWhile(condition) : Renvoie une collection contenant les premiers éléments de la collection source tant que la condition est vraie.
  • Union(otherCollection) : Ajoute la collection en paramètre à la fin de la collection source.
  • Where(condition) : Filtre la collection en ne renvoyant que les éléments pour lesquels la condition est vraie.

 

Les principales méthodes énumérant la collection

  • Any([condition]) : Indique si la collection contient au minimum un élément [qui vérifie la condition]. L’énumération s’arrête au premier élément.
  • Average([selector]) / Min([selector]) / Max([selector]) : Calcule la moyenne / le minimum / la maximum de la collection. L’appel énumère intégralement la collection.
  • Count([condition]) : Compte le nombre d’éléments de la collection [qui vérifient la condition]. Si la condition n’est pas fournie et que la collection implémente ICollection, cet appel n’effectue pas d’énumération. Dans le cas contraire, l’appel énumère intégralement la collection.
  • First([condition]) : Renvoie le premier élément de la collection [vérifiant la condition]. Si la collection est vide [ou qu’aucun élément ne vérifie la condition], une exception est levée. L’appel énumère la collection et s’arrête au premier élément.
  • FirstOrDefault([condition]) : Cette méthode est identique à First([condition]), à ceci près qu’au lieu de lever une exception, elle renvoie la valeur par défaut du type des éléments de la collection.
  • Last([condition]) / LastOrDefault([condition]) : Renvoie le dernier élément de la collection [vérifiant la condition]. Si la collection implémente IList<T> et qu’aucune condition n’est fournie, l’appel n’énumère pas la collection. Sinon, il énumère intégralement la collection.
  • Single([condition]) / SingleOrDefault([condition]) : Renvoie l’unique élément de la collection [qui vérifie la condition]. Si la collection ne contient aucun élément ou contient plus d’un élément [qui vérifie la condition], la méthode lève une exception (Single) ou renvoie la valeur par défaut (SingleOrDefault). L’appel énumère l’intégralité de la collection.
  • ToArray() / ToList() : Enumère l’intégralité de la collection et la renvoie dans un tableau ou une liste.
  • ToDictionary(keySelector) : Enumère l’intégralité de la collection dans un dictionnaire. Si plusieurs éléments ont la même clé, une exception est levée.
  • ToLookup(keySelector) : Enumère l’intégralité de la collection dans une Lookup, une collection où à chaque clé correspond une collection d’éléments.

 

Points d’attention sur LINQ

Les méthodes n’énumérant pas la collection renvoient une collection de type IEnumerable<T>. Cette collection ne prend que très peu de place en mémoire (si l’on exclut la collection originale), puisque les éléments ne sont pas dupliqués. Cependant, cela signifie également que les calculs seront effectués à chaque énumération de la collection.

Pour cette raison, si la collection est destinée à être énumérée plusieurs fois sur de nombreux éléments, il peut être intéressant de la calculer une fois pour toutes, grâce à des méthodes d’extension comme .ToArray() ou .ToList(). Ces deux méthodes sont quasiment identiques, tant en terme de fonctionnalité qu’en terme de performance. La seule véritable différence entre les deux est le type d’objet retourné. Si des éléments doivent être ajoutés ou retirés de cette collection, il faut utiliser une liste. Dans le cas contraire, un tableau fera tout à fait l’affaire.

 

LazyList<T>

Il n’est pas toujours facile de savoir quand préférer une collection LINQ ou un tableau/une liste résultant de son énumération. J’ai donc décidé de créer une classe avec les avantages des deux. Cette classe, qui implémente IList<T>, ne parcourt la collection que si nécessaire (à l’instar d’une collection LINQ), mais garde en mémoire les valeurs énumérées. Lors de l’énumération suivante, il utilise les valeurs en mémoire. Si l’on énumère au-delà, on continue l’énumération LINQ tout en mettant en mémoire les valeurs nouvellement énumérées. Dans le pire des cas, cette collection est légèrement plus lente. Dans le meilleur des cas, elle est beaucoup plus rapide.

LazyList.cs

LazyList.Enumeration.cs

LazyList.Interface.cs

LazyList.LinqOverrides.cs

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.