[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

• Anonymous
  August 18, 2008
  PingBack from http://informationsfunnywallpaper.cn/?p=1125

• Anonymous
  August 18, 2008
  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));

• Anonymous
  August 18, 2008
  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;

• Anonymous
  August 18, 2008
  Olivier, merci pour la coquille, c'est corrigé.