[Réponse] GQ08 V: révisons les ensembles

Réponse au quizz précédent.

Ce quizz va me permettre de rappeler plusieurs points intéressants:

- Jouer avec les chaînes de caractères est toujours un jeu dangereux d'un point de vue de la performance. N'oublions pas qu'en .Net une chaîne est une collection de caractères en lecture seule (immuable). Les syntaxes utilisant les surcharges d'opérateur (ex: "A" + "B") nous laisse croire à une opération peu coûteuse mais il n'en est rien. Même si beaucoup de gens le savent, rappelons que lorsqu'une concaténation de chaines dépasse 2 arguments, il est largement préférable d'utiliser StringBuilder, string.Format ou autres string.Join.

- Les chaînes de caractères sont des IEnumerable<char> ! Cela parait évident mais pourtant le doute survient lorsque l'on s'aperçoit que l'intellisense de Visual Studio ne présente pas les extensions de Linq (Select, Where, Count, Distinct, etc). Ceci est un choix délibéré afin de ne pas complexifier la vue du type string déjà riche en fonctions et de ne pas apporter la confusion sur un type autant utilisé.
Utilisez s.Cast<string>() pour forcer le typage et accéder aux fonctions de Linq via l'intellisense. voir une ancienne discussion sur le sujet

Venons en à la solution. Vous avez tous proposé de très bonnes idées. Examinons les d'un peu plus près.

Pour la première question (union de tous les caractères distints utilisés dans les différentes chaines), Yoann, comme les suivants d'ailleurs, a donné la solution la plus simple et la plus efficace.

 //All dictincts chars

var dc = (from name in names
     from ch in name
     where ch != ' '
     select char.ToUpper(ch)).Distinct();

Pour information, cette requête résoud le problème en une seule passe d'où l'efficacité.

La seconde requête est plus complexe.

Yoann recherche pour chaque caractère s'il est contenu dans l'ensemble des mots.
Cela fonctionne évidemment mais c'est relativement coûteux.
En effet, si on accumule un ensemble de caractères communs pour chaque chaîne de caractères, celui-ci ne peut que diminuer puisque l'on ne garde que l'intersection. Du coup, on cherche à chaque itération de moins en moins de caractères. Cela dépend évidemment énormément du jeu de données.

Commençons par du classique:

 IEnumerable<char> result = null;

foreach (var n in names)
{
    if (result == null)
        result = n;
    else
        result = result.Intersect(n);
}

En bouclant sur l'ensemble des chaînes, on peut cumuler les intersections un peu comme un calculerait une somme. Il ne restera à la fin que la liste des caractères présents uniquement dans l'ensemble des chaînes.

Linq définit une méthode d'extension .Sum() qui calcule la somme d'une énumération de nombres. Bien évidemment cette méthode ne fonctionne pas avec des non numériques. Linq fournit également une méthode .Aggregate() qui fait exactement le même parcours que .Sum() mais qui vous demande de fournir une expression définissant l'opération à effectuer à chaque itération.

Nous pouvons ainsi écrire:

 var q2 =
    (from n in names
    select n.Cast<Char>()).Aggregate((acc, n) => acc.Intersect(n))

qui donnera exactement le même résultat.

Afin de répondre exactement au quizz, j'ajoute le test excluant les espaces:

 var q2 =
    from c in
        (from n in names
         select n.Cast<Char>()).Aggregate((acc, n) => acc.Intersect(n))
    where c != ' '
    select c;

Pour le mot de la fin, bravo à Miitch pour sa requête certes un peu couteuse mais très originale.