C# – Optimiser les performances des opérations ensemblistes avec la classe HashSet
En tant que concepteur / développeur d’applications de gestion de données avec la plateforme Microsoft .Net et le langage C#, je cherche toujours à optimiser les performances des algorithmes que j’implémente. Dans cet article, je vais vous présenter la classe System.Collections.Generic.HashSet
Les différences fondamentales entres les classes HashSet
- Contrairement à une collection de type List
, une collection de type HashSet ne peut contenir de doublons. L’un de ses constructeurs prend en paramètre un objet de comparaison, créé à partir d’une classe implémentant l’interface IEqualityComparer afin de ne pas ajouter un objet qui existe déjà. - Une collection de type HashSet
permet d’exécuter des opérations ensemblistes de données de manière beaucoup plus performante qu’une collection de type List .
Voici un tableau récapitulatif dont les données sont issues des tests que j’ai réalisés avec le Framework .NET Core 2.2 sur mon PC de développement. Le code exécuté est celui fourni à la fin de cet article. Ces résultats varient plus ou moins d’une exécution à l’autre.
Il est évident que la classe HashSet
Voici le code m’ayant permis d’obtenir ces résultats :
{
// Déclaration et initialisation.
Stopwatch stopwatch;
List<string> listBase = new List<string>();
List<string> listSousEnsemble = new List<string>();
List<string> listString = new List<string>();
HashSet<string> hashSetString = new HashSet<string>();
int nbElements = 50000;
bool result;
// ********************************************************
// ** Alimentation.
// ********************************************************
// Création de la liste de base.
for (int i = 1; i <= nbElements; i++)
{
listBase.Add(Guid.NewGuid().ToString());
}
// Sous-ensemble pour les opérations ensemblistes de données.
listSousEnsemble.AddRange(listBase.Take(listBase.Count / 2));
// Pour changer l'ordre des éléments.
listBase = listBase.OrderBy(o => o).ToList();
// Alimentation de List<string>
stopwatch = Stopwatch.StartNew();
foreach (string uid in listBase)
{
listString.Add(uid);
}
stopwatch.Stop();
Console.WriteLine($"listString - alimentée en {stopwatch.Elapsed.TotalSeconds} secondes");
// Alimentation de HashSet<string>
stopwatch = Stopwatch.StartNew();
foreach (string uid in listBase)
{
hashSetString.Add(uid);
}
stopwatch.Stop();
Console.WriteLine($"hashSetString - alimentée en {stopwatch.Elapsed.TotalSeconds} secondes");
Console.WriteLine(string.Empty);
// ********************************************************
// ********************************************************
// ** Recherche.
// ********************************************************
// List<string>
stopwatch = Stopwatch.StartNew();
foreach (string s in listBase)
{
result = listString.Contains(s);
}
stopwatch.Stop();
Console.WriteLine($"listString - recherche en {stopwatch.Elapsed.TotalSeconds} secondes");
// HashSet<string>
stopwatch = Stopwatch.StartNew();
foreach (string s in listBase)
{
result = hashSetString.Contains(s);
}
stopwatch.Stop();
Console.WriteLine($"hashSetString - recherche en {stopwatch.Elapsed.TotalSeconds} secondes");
Console.WriteLine(string.Empty);
// ********************************************************
// ********************************************************
// ** Intersection.
// ********************************************************
// List<string>
stopwatch = Stopwatch.StartNew();
listString.Intersect(listSousEnsemble);
stopwatch.Stop();
Console.WriteLine($"listString - intersection en {stopwatch.Elapsed.TotalSeconds} secondes");
// HashSet<string>
stopwatch = Stopwatch.StartNew();
hashSetString.Intersect(listSousEnsemble);
stopwatch.Stop();
Console.WriteLine($"hashSetString - intersection en {stopwatch.Elapsed.TotalMilliseconds} millisecondes");
Console.WriteLine(string.Empty);
// ********************************************************
// ********************************************************
// ** Union.
// ********************************************************
// List<string>
stopwatch = Stopwatch.StartNew();
listString.Union(listSousEnsemble);
stopwatch.Stop();
Console.WriteLine($"listString - union en {stopwatch.Elapsed.TotalSeconds} secondes");
// HashSet<string>
stopwatch = Stopwatch.StartNew();
hashSetString.Union(listSousEnsemble);
stopwatch.Stop();
Console.WriteLine($"hashSetString - union en {stopwatch.Elapsed.TotalMilliseconds} millisecondes");
Console.WriteLine(string.Empty);
// ********************************************************
// ********************************************************
// ** Exclusion.
// ********************************************************
// List<string>
stopwatch = Stopwatch.StartNew();
listString.Except(listSousEnsemble);
stopwatch.Stop();
Console.WriteLine($"listString - exclusion en {stopwatch.Elapsed.TotalSeconds} secondes");
// HashSet<string>
stopwatch = Stopwatch.StartNew();
hashSetString.Except(listSousEnsemble);
stopwatch.Stop();
Console.WriteLine($"hashSetString - exclusion en {stopwatch.Elapsed.TotalMilliseconds} millisecondes");
Console.WriteLine(string.Empty);
// ********************************************************
// ********************************************************
// ** Suppression.
// ********************************************************
// List<string>
stopwatch = Stopwatch.StartNew();
foreach (string s in listBase)
{
listString.Remove(s);
}
stopwatch.Stop();
Console.WriteLine($"listString - suppression en {stopwatch.Elapsed.TotalSeconds} secondes");
// HashSet<string>
stopwatch = Stopwatch.StartNew();
foreach (string s in listBase)
{
hashSetString.Remove(s);
}
stopwatch.Stop();
Console.WriteLine($"hashSetString - suppression en {stopwatch.Elapsed.TotalSeconds} secondes");
// ********************************************************
}
catch (Exception aEx)
{
Console.WriteLine(aEx.Message);
}
finally
{
Console.ReadKey();
}