C# – Dictionnaires

Quelques raccourcis :

Exemple sans dictionnaire
Exemple avec dictionnaire

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) :

using System;
  
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");

static (string Nom, int Nb)[] CompterOccurrences(string [] mots)
{
   // ...
}

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

Pour chaque mot m dans mots
- Chercher m dans un tableau (ou une autre collection) de paires (nom,n) où n est le nombre d'occurrences de nom jusqu'ici
- Si nous trouvons ce mot, alors incrémenter le nombre d'occurrences qui lui est associé
- Si nous ne le trouvons pas, alors ajouter à la collection une nouvelle paire (m,n)
Enfin, retourner la collection résultante

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 ();
   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 https://dotnetfiddle.net/CeKgNl 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

Refaisons 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 :

using system;
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");

static (string Nom, int Nb)[] CompterOccurrences(string [] mots)
{
   // ...
}

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

Pour chaque mot m dans mots
- Vérifier si la collection contient une clé m
- Si oui, alors incrémenter le nombre d'occurrences qui lui est associé
- Sinon, alors ajouter à la collection une nouvelle paire (m,n)
Enfin, retourner la collection résultante

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 ();
   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 https://dotnetfiddle.net/jNvvbK 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.