C# – Dictionnaires

Quelques raccourcis :

Avec C# comme avec la plupart des langages contemporains, il existe dans la bibliothèque standard du langage (le cadriciel .NET dans ce cas) des types jouant le rôle d'un tableau associatif.

Une telle structure de données a pour rôle de mettre en correspondance une clé et une valeur (ou plusieurs valeurs, selon les types de tableaux associatifs).

Ce petit document présente l'un des plus connus de ces types pour C#, soit le type Dictionary<K,V>.

Exemple sans dictionnaire

Supposons que nous souhaitions compter le nombre d'occurrences de chaque mot dans une séquence de mots (c'est l'exemple classique dans le genre). Pour simplifier le portrait, nous présumerons le code client suivant (notez que j'utiliserai un tableau d'uplets comme type de retour pour simplifier le propos) :

static (string Nom, int Nb)[] CompterOccurrences(string [] mots)
{
   // ...
}
static void Main(string[] args)
{
   string [] mots = new []
   {
      "bonjour", "coucou", "allo", "coucou", "yo", "bonjour", "coucou"
   };
   foreach(var (Mot, Nb) in CompterOccurrences(mots))
      Console.WriteLine($"Le mot {Mot} apparaît {Nb} fois");
}

Si nous souhaitons implémenter CompterOccurrences() « manuellement », sans passer par un tableau associatif, nous devrons faire quelque chose comme :

Une implémentation possible serait la suivante. J'utiliserai une List<(string,int)> pour simplifier la logique de redimensionnement lors d'une insertion :

// ...
static int TrouverIndice(List<(string Mot, int Nb)> mots, string mot)
{
   for(int i = 0; i != mots.Count; ++i)
     if(mots[i].Mot == mot)
         return i;
   return -1;
}
static (string Nom, int Nb)[] CompterOccurrences(string [] mots)
{
   List <(string Mot, int Nb)> lst = new List<(string,int)>();
   foreach(string mot in mots)
   {
      int ndx = TrouverIndice(lst, mot);
      if(ndx == -1)
         lst.Add((mot, 1)); // notez les double parenthèses (pour créer un uplet)
      else
         lst[ndx] = (mot, lst[ndx].Nb + 1);
   }
   return lst.ToArray();
}

À l'exécution avec dotnetfiddle, j'obtiens :

Le mot bonjour apparaît 2 fois
Le mot coucou apparaît 3 fois
Le mot allo apparaît 1 fois
Le mot yo apparaît 1 fois

Exemple avec dictionnaire

Refaisos l'exercice, mais avec un dictionnaire cette fois. J'ai conservé le même code client, répété ici pour faciliter le repérage :

static (string Nom, int Nb)[] CompterOccurrences(string [] mots)
{
   // ...
}
static void Main(string[] args)
{
   string [] mots = new []
   {
      "bonjour", "coucou", "allo", "coucou", "yo", "bonjour", "coucou"
   };
   foreach(var (Mot, Nb) in CompterOccurrences(mots))
      Console.WriteLine($"Le mot {Mot} apparaît {Nb} fois");
}

Si nous souhaitons implémenter CompterOccurrences() avec un tableau associatif, nous devrons faire quelque chose comme :

C'est la même logique que précédemment, à ceci près que la fouille sera faite par la collection (qui est spécialisée justement dans ce type de traitement) Une implémentation possible serait la suivante :

// ...
static (string Nom, int Nb)[] CompterOccurrences(string [] mots)
{
   Dictionary<string, int> dictio = new Dictionary<string,int>();
   foreach(string mot in mots)
      if(dictio.ContainsKey(mot))
         dictio[mot]++;
      else
         dictio.Add(mot, 1);
   (string, int) [] tab = new (string, int)[dictio.Count];
   int i = 0;
   foreach(var p in dictio)
      tab[i++] = (p.Key, p.Value);
   return tab;
}

Outre la logique pour créer le tableau de paires à la fin du calcul, c'est plus simple que précédemment. À l'exécution avec dotnetfiddle, j'obtiens :

Le mot bonjour apparaît 2 fois
Le mot coucou apparaît 3 fois
Le mot allo apparaît 1 fois
Le mot yo apparaît 1 fois

C'est tout de même plus simple.

Lectures complémentaires

Quelques liens pour enrichir le propos.


Valid XHTML 1.0 Transitional

CSS Valide !