[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.

Comments (4)

  1. Olivier says:

    Joli le coup de l’aggregate avec le cast<char> pour la seconde réponse !

    juste une coquille, il manque des parenthèses à la définition de "q2" (la version 1 qui ne contrôle pas les espaces) autour du from/select sinon l’aggregate ne passe pas :

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

  2. Pour q1, je trouve que c’est quand même plus classe (même si c’est moins lisible d’utiliser un SelectMany comme je l’ai fait).

    var q1 = (from c in names.SelectMany(n => n)

             where c != ‘ ‘

             select char.ToUpper(c)).Distinct();

    Pour q2, je pense qu’il est préférable de caster le string en IEnumerable<char> plutôt que de caster chaque caractère du string en char.

    var q2 = from c in names.Cast<IEnumerable<char>>().Aggregate((a, b) => a.Intersect(b))

            where c != ‘ ‘

            select c;

  3. Mitsu Furuta says:

    Olivier, merci pour la coquille, c’est corrigé.

Skip to main content