Bienvenue à Blogs CodeS-SourceS Identification | Inscription | Aide

Abonnements

Quizz 10 - Où placer le Where

Ce quizz est un peu spécial car il est inclut dans "un vrai post".

Où placer le where ? Cette question a l'air très simple mais ce n'est pourtant pas si facile que ça.

Reprenons la solution que je propose sur le dernier quizz de Mitsu :

names.Select(n => (IEnumerable<char>)n).Aggregate((a, b) => a.Intersect(b)).Where(c => c != ' ');

Je place donc le where à la fin. Ce qui est peut-être dommage car cela implique que je vais faire l'intersection avec ' ' avant de le supprimer.

Je pourrais effectivement placer mon Where bien avant :

names.Select(n => ((IEnumerable<char>)n).Where(c => c != ' ')).Aggregate((a, b) => a.Intersect(b));

Oui mais cette dernière solution fait que pour chaque caractère de chacune de mes chaînes de caractères, je vais le comparer avec ' '.

On pourrait alors se dire que vu que l'on va faire une intersection, il serait plus judicieux de ne faire le Where que sur la première chaîne de caractère :

names.Take(1).Select(n => n.Where(c => c != ' ')).Union(names.Skip(1).Select(n => (IEnumerable<char>)n)).Aggregate((a, b) => a.Intersect(b));

Ou

names.Select((n, i) => i == 0 ? n.Where(c => c != ' ') : (IEnumerable<char>)n).Aggregate((a, b) => a.Intersect(b));

Ou alors inclure directement le Where dans le Intersect en utilisant la version avec le IEqualityComparer.

Voici le tests que j'ai réalisé :

var q1 = names.Select(n => (IEnumerable<char>)n).Aggregate((a, b) => a.Intersect(b)).Where(c => c != ' ');

var q2 = names.Select(n => ((IEnumerable<char>)n).Where(c => c != ' ')).Aggregate((a, b) => a.Intersect(b));

var q3 = names.Take(1).Select(n => n.Where(c => c != ' ')).Union(names.Skip(1).Select(n => (IEnumerable<char>)n)).Aggregate();

var q4 = names.Select((n, i) => i == 0 ? n.Where(c => c != ' ') : (IEnumerable<char>)n).Aggregate((a, b) => a.Intersect(b));

 

var equalityComparer = new ComparerWithForbiddenValues<char> { ForbiddenValues = new char[] { ' ' } };

 

var q5 = names.Select(n => (IEnumerable<char>)n).Aggregate((a, b) => a.Intersect(b, equalityComparer));

 

int un = Environment.TickCount;

for (int i = 0; i < 100000; i++)

    foreach (var c in q1) ;

 

int deux = Environment.TickCount;

Console.WriteLine(deux - un);

for (int i = 0; i < 100000; i++)

    foreach (var c in q2) ;

 

int trois = Environment.TickCount;

Console.WriteLine(trois - deux);

for (int i = 0; i < 100000; i++)

    foreach (var c in q3) ;

 

int quatre = Environment.TickCount;

Console.WriteLine(quatre - trois);

for (int i = 0; i < 100000; i++)

    foreach (var c in q4) ;

 

int cinq = Environment.TickCount;

Console.WriteLine(cinq - quatre);

for (int i = 0; i < 100000; i++)

    foreach (var c in q5) ;

 

int six = Environment.TickCount;

Console.WriteLine(six - cinq);

avec

public class ComparerWithForbiddenValues<T> : IEqualityComparer<T>

{

    private IEqualityComparer<T> _equalityComparer;

    private IEnumerable<T> _forbiddenValues;

 

    public ComparerWithForbiddenValues()

    {

    }

 

    public ComparerWithForbiddenValues(IEqualityComparer<T> equalityComparer)

    {

        _equalityComparer = equalityComparer;

    }

 

    public IEnumerable<T> ForbiddenValues

    {

        get { return _forbiddenValues; }

        set { _forbiddenValues = value; }

    }

 

    public bool Equals(T x, T y)

    {

        if (_equalityComparer == null)

            return x.Equals(y) && !_forbiddenValues.Any(v => v.Equals(x));

        return _equalityComparer.Equals(x, y) && !_forbiddenValues.Any(v => _equalityComparer.Equals(v, x));

    }

 

    public int GetHashCode(T obj)

    {

        if (_equalityComparer == null)

            return obj.GetHashCode();

        return _equalityComparer.GetHashCode(obj);

    }

}

Tout d'abord, j'ai executé ce test avec

var names = new List<string> { "Mitsuru FURUTA", "Dick LANTIM", "Pierre LAGARDE" };

Le résultat est le suivant :

578
703
609
609
828

Ensuite, j'ai executé ce test sur une liste plus grande :

var names = new List<string> { "Mitsuru FURUTA", "Dick LANTIM", "Pierre LAGARDE" };

for (int i = 0; i < 100; i++)

    names.Add("Mitsuru FURUTA");

Le résultat est alors le suivant :

21344
26609
781
22219
35281

Pourquoi un tel écart ? C'est l'objet de mon quizz 10. Enjoy Big Smile

Enfin dans le test suivant (sans l'espace qu'on veut supprimer),

var names = new List<string> { "MitsuruFURUTA", "Dick LANTIM", "Pierre LAGARDE" };

les résultats sont les suivants :

532
687
609
610
797

Maintenant, reprenons le test un mais en "surchargeant" la méthode Intersect :

public static class MyExtension

{

    public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second)

    {

        return from e in Enumerable.Intersect(first, second)

               where SimuleUnIntersectPlusLong(e)

               select e;

    }

    public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)

    {

        return from e in Enumerable.Intersect(first, second, comparer)

               where SimuleUnIntersectPlusLong(e)

               select e;

    }

    public static bool SimuleUnIntersectPlusLong<TSource>(TSource e)

    {

        for (int i = 0; i < 100000; i++) ;

        return true;

    }

}

Pour mes tests, je suis alors passé d'une boucle de 100 000 itérations à 1 000. Les résultats sont les suivants :

2453
2422
2438
2438
2422

Les tests variant en fonction des autres process qui tournent simultanément, pour les résultats, j'ai pris le minimum de 3 exécutions.

Dans tous les cas, il est intéressant de constater que la position du where influe sur les performances en fonction du contexte.

Comme me l'a justement fait remarqué Mitsu, cela n'est pas relatif à LINQ. La performance dépend du jeu de données.

Ce post vous a plu ? Ajoutez le dans vos favoris pour ne pas perdre de temps à le retrouver le jour où vous en aurez besoin :

Publié lundi 18 août 2008 21:18 par Matthieu MEZIL

Classé sous : , , ,

Commentaires

# re: Quizz 10 - Où placer le Where @ mardi 19 août 2008 23:03

Allez, je vais jouer mon pénible encore une fois... q3 est plus rapide parce que les autres sont vraiment anormalement lents :-)

Voici - comme d'habitude sans LINQ - un code beaucoup plus rapide:

public static IEnumerable

<char> GetCommonX(IEnumerable<string> names)

{

   if (names == null)

       return Enumerable.Empty<char>();

   Dictionary<char, string=""> dict = null;

   List<char> toRemove = null;

   foreach (string name in names)

   {

       if (dict == null)

       {

           dict = new Dictionary<char, string="">();

           for (int i = 0; i &lt; name.Length; i++)

           {

               if (nameIdea == ' ')

                   continue;

               dict[nameIdea] = null;

               if (dict.Count == 0)

                   return Enumerable.Empty<char>();

           }

           toRemove = new List<char>();

       }

       else

       {

           toRemove.Clear();

           foreach(char c in dict.Keys)

           {

               if (name.IndexOf(c) &lt; 0)

               {

                   toRemove.Add(c);

               }

           }

           for (int i = 0; i &lt; toRemove.Count; i++)

           {

               dict.Remove(toRemoveIdea);

           }

           if (dict.Count == 0)

               return Enumerable.Empty<char>();

       }

   }

   return dict.Keys;

}

Avec le benchmark ci dessus, j'obtiens environ 16 vs 641 (q3)...

Note que ce code s'arrête très vite lorsqu'il n'y a plus rien à faire, ce qui fait que plus il y a de chaînes et plus elles sont longues, et plus il va vite (forcément puisque les intersections se réduisent!), ce qui n'est pas le cas d'aucun autre code ici présent (y compris q3 qui rattrape les autres quand les chaînes sont distribuées de manière aléatoires).

PS: sur ComparerWithForbiddenValues, il vaut mieux déclarer le premier constructeur comme ceci:

public ComparerWithForbiddenValues()

:this(EqualityComparer<T>.Default)

{

}

ce qui te permet d'enlever les tests sur _equalityComparer à null.

smo

# re: Quizz 10 - Où placer le Where @ mardi 19 août 2008 23:12

euh, les ampoules correspondent à [ i ]...

smo

# re: Quizz 10 - Où placer le Where @ mardi 19 août 2008 23:15

ok ok mais pourquoi q3 est-elle beaucoup plus rapide que les autres lors de mon 2ème test ?

Matthieu MEZIL

# re: Quizz 10 - Où placer le Where @ mardi 19 août 2008 23:37

hmm... je ne sais pas trop ce que tu attends comme réponse. Parce que le where n'est fait que sur la première chaîne?

smo

# re: Quizz 10 - Où placer le Where @ mercredi 20 août 2008 08:59

C'est également le cas dans q4 qui est pourtant beaucoup plus long.

Matthieu MEZIL

# re: Quizz 10 - Où placer le Where @ mercredi 20 août 2008 15:58

Le Union fait automatiquement un Distinct, ce qui fait qu'on se retrouve avant le Intersect avec 4 éléments :

MitsuruFURUTA

Dick LANTIM

Pierre LAGARDE

Mitsuru FURUTA

au lieu de 103.

Matthieu MEZIL

Les commentaires anonymes sont désactivés

Les 10 derniers blogs postés

- Merci par Blog de Jérémy Jeanson le 10-01-2019, 20:47

- Office 365: Script PowerShell pour auditer l’usage des Office Groups de votre tenant par Blog Technique de Romelard Fabrice le 04-26-2019, 11:02

- Office 365: Script PowerShell pour auditer l’usage de Microsoft Teams de votre tenant par Blog Technique de Romelard Fabrice le 04-26-2019, 10:39

- Office 365: Script PowerShell pour auditer l’usage de OneDrive for Business de votre tenant par Blog Technique de Romelard Fabrice le 04-25-2019, 15:13

- Office 365: Script PowerShell pour auditer l’usage de SharePoint Online de votre tenant par Blog Technique de Romelard Fabrice le 02-27-2019, 13:39

- Office 365: Script PowerShell pour auditer l’usage d’Exchange Online de votre tenant par Blog Technique de Romelard Fabrice le 02-25-2019, 15:07

- Office 365: Script PowerShell pour auditer le contenu de son Office 365 Stream Portal par Blog Technique de Romelard Fabrice le 02-21-2019, 17:56

- Office 365: Script PowerShell pour auditer le contenu de son Office 365 Video Portal par Blog Technique de Romelard Fabrice le 02-18-2019, 18:56

- Office 365: Script PowerShell pour extraire les Audit Log basés sur des filtres fournis par Blog Technique de Romelard Fabrice le 01-28-2019, 16:13

- SharePoint Online: Script PowerShell pour désactiver l’Option IRM des sites SPO non autorisés par Blog Technique de Romelard Fabrice le 12-14-2018, 13:01