Hashtable, Dictionary<TKey, TValue> etc.

Rentrons directement dans le vif du sujet : Je ne vous présente plus la classe Hashtable, ni la classe Dictionary<TKey, TValue>. Et bien j'ai fait une petite constatation et je voulais vous en faire part ô chers lecteurs. Supposons qu'à partir de 2 collections diverses, nous souhaitions en peupler une troisième :

// Notre 1ère collection :
// On crée 3 personnes et on les ajoute à notre 1ère collection
Personne jaco = new Personne("Pastorius", "John Francis Anthony", new DateTime(1951, 12, 1));
Personne marcus = new Personne("Miller", "Marcus", new DateTime(1959, 6, 14));
Personne victor = new Personne("Wooten", "Victor Lemonte", new DateTime(1964, 11, 8));

List<Personne> topBassists = new List<Personne>();
topBassists.Add(jaco);
topBassists.Add(marcus);
topBassists.Add(victor);

// Notre 2è collection
// On récupère à partir d'une source tierce, 3 autres personnes.
Personne s = new Personne("Clarck", "Stanley", new DateTime(1948, 10, 17));
Personne m = new Personne("Miller", "Marcus", new DateTime(1959, 6, 14));
Personne v = new Personne("Wooten", "Victor Lemonte", new DateTime(1964, 11, 8));

List<Personne> smvBassists = new List<Personne>();
smvBassists.Add(s);
smvBassists.Add(m);
smvBassists.Add(v);

//..
// Enfin on souhaite récupérer une liste de personnes avec comme source les 2 listes précédentes.
List<Personne> jazzFestival = new List<Personne>();
jazzFestival.AddRange(topBassists);
jazzFestival.AddRange(smvBassists);

Vous l'avez deviné on va se retrouver avec des doublons dans notre liste.

C'est là qu'intervient la classe hashtable ou Dictionary<TKey, TValue>. Elle va nous permettre de gérer les doublons :

Dictionary<string, Personne> jazzFestivalTriee = new Dictionary<string, Personne>();

foreach (Personne p in jazzFestival)
{
if (!jazzFestivalTriee.ContainsKey(p.Nom))
jazzFestivalTriee.Add(p.Nom, p);
}

Et là, on se retrouve avec une collection d'éléments uniques. Top non ? Bon ok, il n'y a pas de quoi s'énerver :) Bon alors le petit truc que j'ai trouvé c'est qu'on peut se passer de la condition if (!jazzFestivalTriee.ContainsKey(p.Nom)) , sans pour autant se faire jeter une exception à la figure. En fait il faut simplement passer par l'indexeur du hashtable / Dictionary<TKey, TValue> :

foreach (Personne p in jazzFestival)
{
jazzFestivalTriee[p.Nom] = p;
}

Et le résultat est identique.

Chouette non ? Et en plus on y gagne en perf (enfin on est dans l'ordre du chouïa :) Voici ce petit tableau récapitulatif :

	Dictionary<Tkey, Tvalue>	Hashtable
Avec condition if	1426	2522
Sans condition if	1262	2217
Gain observé (en %)	12,99524564	13,75732972

Quelques remarques : tout d'abord, sur quel code ont été faites les mesures :

List<Personne> listeAtrier = new List<Personne>();

for (int i = 0; i < 5300000; i++) // 5,3 millions
listeAtrier.Add(new Personne(i.ToString(), (i * 2).ToString(), new DateTime(1981, 11, 23)));

for (int i = 0; i < 1500000; i++) // 1,5 millions
listeAtrier.Add(new Personne(i.ToString(), (i * 2).ToString(), new DateTime(1981, 11, 23)));

Donc j'ai crée une liste de 'personne' 5,3 millions d'items et puis j'en ai ajouté encore 1,5 millions qui sont identiques à ce de la première (pour qu'il y est des doublons dans la liste). La suite du code n'a rien de surprenant :

Hashtable listeTriee = new Hashtable();
//Dictionary<string, Personne> listeTriee = new Dictionary<string, Personne>();

Stopwatch timer = new Stopwatch();
timer.Start();
foreach (Personne p in listeAtrier)
{
//if (!listeTriee.ContainsKey(p.Nom))
//listeTriee.Add(p);
listeTriee[p.Nom] = p;
}
timer.Stop();
Console.WriteLine(listeAtrier.Count);
Console.WriteLine(listeTriee.Count);
Console.WriteLine(timer.ElapsedMilliseconds);

Voilà, pour d'autres optimisations, vous pouvez aller ici.