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 et les performances qu’elle propose par rapport à la classe System.Collections.Generic.List lors d’opérations ensemblistes de données.
Les différences fondamentales entres les classes HashSet et List sont les suivantes :

  • 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 propose des performances très importantes lors d’opérations ensemblistes par rapport à la classe List, à l’exception de l’ajout de données. En effet lors de l’ajout de données dans une collection de type HashSet, il est vérifié que l’élément à ajouter n’est pas présent dans la collection. Si un élément déjà existant est ajouté, alors l’ajout est ignoré sans qu’aucune exception ne soit levée.

Voici le code m’ayant permis d’obtenir ces résultats :

try
{
    // 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();
}

About: James RAVAILLE

Travaillant avec la plateforme Microsoft .NET depuis 2002, j’alterne les missions de formation et d’ingénierie avec cette plateforme. J’écris ce blog pour transmettre mes connaissances à tout développeur, qu’il soit débutant ou expérimenté.