Pourquoi êtes où et sélectionnez surperformant il suffit de sélectionner ?

Question

J'ai une classe, comme ceci:

public class MyClass
{
    public int Value { get; set; }
    public bool IsValid { get; set; }
}

_{En réalité, il est beaucoup plus grande, mais cela recrée le problème (étrangeté).}

Je veux obtenir la somme des Value, où l'instance est valide. Jusqu'à présent, j'ai trouvé deux solutions à cela.

Le premier est celui-ci:

int result = myCollection.Where(mc => mc.IsValid).Select(mc => mc.Value).Sum();

Le second, cependant, est la suivante:

int result = myCollection.Select(mc => mc.IsValid ? mc.Value : 0).Sum();

Je veux obtenir la méthode la plus efficace. J'ai d'abord pensé que le second serait plus efficace. Ensuite, la partie théorique de moi a commencé à aller "eh Bien, l'un est O(n + m + m), l'autre est O(n + n). La première, on devra faire mieux avec plus de invalides, tandis que le second, on devra faire mieux avec moins". Je pensais qu'ils feraient tout aussi. EDIT: Et puis @Martin a souligné que le " Où " et le Sélectionner étaient combinés, de sorte qu'il devrait en fait être en O(m + n). Cependant, si vous regardez ci-dessous, il semble que ce n'est pas lié.

---

Donc je l'ai mis à l'épreuve.

_{(C'est+ de 100 lignes, j'ai donc pensé que c'était mieux de poster comme un Essentiel).}
Les résultats ont été... intéressant.

_{Avec 0% de la cravate de la tolérance:}

Les échelles sont en faveur de l' Select et Where, par environ 30 points.

How much do you want to be the disambiguation percentage?

_{Avec 2% de la cravate de la tolérance:}

C'est la même chose, sauf que pour certains, ils étaient à moins de 2%. Je dirais que c'est un minimum de marge d'erreur.
et 0 maintenant avoir juste une ~20 points d'avance.




_{Avec 5% de la cravate de la tolérance:}

C'est ce que je dirais à ma marge d'erreur maximale. Il fait un peu mieux pour l' Starting benchmarking., mais pas beaucoup.




_{Avec 10% de la cravate de la tolérance:}

C'est moyen de sortir de ma marge d'erreur, mais je suis toujours intéressé par le résultat. Parce qu'il donne l' Ties: 0 et
de la vingt points d'avance, il avait depuis un moment maintenant.

Where + Select: 65

_{Avec 25% de la cravate de la tolérance:}

C'est une façon, de manière à sortir de ma marge d'erreur, mais je suis toujours intéressé par le résultat, parce que l'
et Select: 36 encore (presque) garder leurs 20 points d'avance. Il semble que c'est le surclassant dans une quelques-uns, et c'est ce que donner de la tête.




---

Maintenant, j'imagine que 20 points d'avance, est venu à partir du milieu, où ils sont à la fois lié à obtenir autour de la même performance. Je pourrais essayer de l'enregistrer, mais il serait un chargement entier de l'information. Un graphique serait mieux, je pense.

Donc, c'est ce que j'ai fait.

Il montre que l' ligne garde régulière (prévu) et que l' Select ligne de grimpe (prévu). Cependant, ce qui m'intrigue, c'est pourquoi il ne rencontre pas l' Where à 50 ou plus tôt: en fait, je m'attendais plus tôt que 50, comme un supplément, agent recenseur devait être créé pour l' How much do you want to be the disambiguation percentage? et
. Je veux dire, ce qui montre l'20 points d'avance, mais ça n'explique pas pourquoi. Cela, je pense, c'est le point principal de ma question.

Pourquoi faut-il se comporter comme cela? Dois-je lui faire confiance? Si non, dois-je utiliser l'autre ou les autres?

---

@KingKong mentionné dans les commentaires, vous pouvez également utiliser 2s'surcharge qui prend un lambda. Donc, mes deux options sont maintenant changé à cela:

D'abord:

Deuxième:

Starting benchmarking.

Je vais le faire un peu plus court, mais:




Le vingt-point est toujours là, le sens qu'il n'a pas à faire avec l' Ties: 6 et
combinaison l'a souligné @Marcin dans les commentaires.

_{Merci pour la lecture par le biais de mon mur de texte! Aussi, si vous êtes intéressés, voici la version modifiée qui enregistre au format CSV Excel prend en.}

Answer 1

Select réitère une fois de plus de l'ensemble et, pour chaque élément, effectue une branche conditionnelle (vérification de validité) et d'un + de l'opération.

Where+Select crée un itérateur qui ignore les éléments invalides n'est pas yield entre eux), la réalisation d'un + seulement sur les questions pertinentes.

Ainsi, le coût pour un Select est:

t(s) = n * ( cost(check valid) + cost(+) )

Et pour Where+Select:

t(ws) = n * ( cost(check valid) + p(valid) * (cost(yield) + cost(+)) )

Où:

• p(valid) est la probabilité qu'un élément de la liste est valide.
• cost(check valid) est le coût de la branche qui vérifie la validité de
• cost(yield) est le coût de construction du nouvel état de l' where itérateur, qui est plus complexe que la simple itérateur qui l' Select version utilise.

Comme vous pouvez le voir, pour un n, Select version est une constante, alors que l' Where+Select version est une équation linéaire avec p(valid) comme une variable. Les valeurs réelles des coûts de déterminer le point d'intersection des deux lignes, et depuis cost(yield) peut être différent de cost(+), ils n'ont pas nécessairement se croisent en p(valid)=0.5.

Answer 2

Voici une explication en profondeur de ce qui est à l'origine du calendrier-des différences.

---

L' Sum() fonction pour IEnumerable<int> ressemble à ceci:

public static int Sum(this IEnumerable<int> source)
{
    int sum = 0;
    foreach(int item in source)
    {
        sum += item;
    }
    return sum;
}

En C#, foreach est juste sucre syntaxique pour .Net version d'un itérateur, IEnumerator<T> (à ne pas confondre avec IEnumerable<T>). Donc le code ci-dessus est en fait traduit à ceci:

public static int Sum(this IEnumerable<int> source)
{
    int sum = 0;

    IEnumerator<int> iterator = source.GetEnumerator();
    while(iterator.MoveNext())
    {
        int item = iterator.Current;
        sum += item;
    }
    return sum;
}

Rappelez-vous, les deux lignes de code que vous êtes à la comparaison sont les suivants

int result1 = myCollection.Where(mc => mc.IsValid).Sum(mc => mc.Value);
int result2 = myCollection.Sum(mc => mc.IsValid ? mc.Value : 0);

---

Maintenant, voici le kicker:

LINQ utilise l'exécution différée. Ainsi, même s'il peut apparaître que l' result1 parcourt la collection deux fois, il fait seulement parcourt qu'une seule fois. L' Where() condition est effectivement appliqué lors de l' Sum(), à l'intérieur de l'appel à MoveNext() (Ce qui est possible grâce à la magie de l' yield return).

Cela signifie que, pour result1, le code à l'intérieur de l' while boucle,

{
    int item = iterator.Current;
    sum += item;
}

n'est exécuté qu'une seule fois pour chaque élément avec l' mc.IsValid == true. Par comparaison, result2 execute ce code pour chaque élément de la collection. C'est pourquoi, result1 est généralement plus rapide.

(Bien noter que l'appel de l' Where() état dans MoveNext() a encore quelques petits frais généraux, de sorte que si la plupart des articles ont mc.IsValid == true, result2 sera effectivement plus rapide!)

---

Espérons maintenant il est clair pourquoi result2 est généralement plus lent. Maintenant, je voudrais expliquer pourquoi je l'ai dit dans les commentaires que ces LINQ comparaisons de performances n'a pas d'importance.

La création d'une expression LINQ n'est pas cher. L'appel de déléguer des fonctions n'est pas cher. L'allocation et de boucler sur un itérateur est bon marché. Mais c'est encore moins cher de ne pas faire ces choses. Ainsi, si vous trouvez qu'une LINQ déclaration est le goulot d'étranglement dans votre programme, dans mon expérience, à le réécrire sans LINQ sera toujours le rendre plus rapide que l'une des diverses méthodes LINQ.

Donc, votre LINQ flux de travail devrait ressembler à ceci:

1. Utiliser LINQ partout.
2. De profil.
3. Si le profileur dit LINQ est la cause d'un goulot d'étranglement, la réécriture de ce morceau de code sans LINQ.

Heureusement, LINQ, les goulots d'étranglement sont rares. Heck, les goulots d'étranglement sont rares. J'ai écrit des centaines de LINQ déclarations dans les dernières années, et ont fini par remplacer <1%. Et la plupart de ceux qui ont été en raison de LINQ2EF's mauvaise SQL optimisation, plutôt que d'être LINQ faute.

Donc, comme toujours, d'écriture clair et logique du premier code, et attendre jusqu'à après que vous avez profilé à vous soucier de micro-optimisations.

Answer 3

Drôle de chose. Savez-vous comment est - Sum(this IEnumerable<TSource> source, Func<TSource, int> selector) ? Il utilise Select méthode!

public static int Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector)
{
    return source.Select(selector).Sum();
}

Donc en fait, tout devrait fonctionner presque le même. J'ai fait une recherche rapide sur mon propre, et voici les résultats:

Where -- mod: 1 result: 0, time: 371 ms
WhereSelect -- mod: 1  result: 0, time: 356 ms
Select -- mod: 1  result 0, time: 366 ms
Sum -- mod: 1  result: 0, time: 363 ms
-------------
Where -- mod: 2 result: 4999999, time: 469 ms
WhereSelect -- mod: 2  result: 4999999, time: 429 ms
Select -- mod: 2  result 4999999, time: 362 ms
Sum -- mod: 2  result: 4999999, time: 358 ms
-------------
Where -- mod: 3 result: 9999999, time: 441 ms
WhereSelect -- mod: 3  result: 9999999, time: 452 ms
Select -- mod: 3  result 9999999, time: 371 ms
Sum -- mod: 3  result: 9999999, time: 380 ms
-------------
Where -- mod: 4 result: 7500000, time: 571 ms
WhereSelect -- mod: 4  result: 7500000, time: 501 ms
Select -- mod: 4  result 7500000, time: 406 ms
Sum -- mod: 4  result: 7500000, time: 397 ms
-------------
Where -- mod: 5 result: 7999999, time: 490 ms
WhereSelect -- mod: 5  result: 7999999, time: 477 ms
Select -- mod: 5  result 7999999, time: 397 ms
Sum -- mod: 5  result: 7999999, time: 394 ms
-------------
Where -- mod: 6 result: 9999999, time: 488 ms
WhereSelect -- mod: 6  result: 9999999, time: 480 ms
Select -- mod: 6  result 9999999, time: 391 ms
Sum -- mod: 6  result: 9999999, time: 387 ms
-------------
Where -- mod: 7 result: 8571428, time: 489 ms
WhereSelect -- mod: 7  result: 8571428, time: 486 ms
Select -- mod: 7  result 8571428, time: 384 ms
Sum -- mod: 7  result: 8571428, time: 381 ms
-------------
Where -- mod: 8 result: 8749999, time: 494 ms
WhereSelect -- mod: 8  result: 8749999, time: 488 ms
Select -- mod: 8  result 8749999, time: 386 ms
Sum -- mod: 8  result: 8749999, time: 373 ms
-------------
Where -- mod: 9 result: 9999999, time: 497 ms
WhereSelect -- mod: 9  result: 9999999, time: 494 ms
Select -- mod: 9  result 9999999, time: 386 ms
Sum -- mod: 9  result: 9999999, time: 371 ms

Pour les implémentations suivantes:

result = source.Where(x => x.IsValid).Sum(x => x.Value);
result = source.Select(x => x.IsValid ? x.Value : 0).Sum();
result = source.Sum(x => x.IsValid ? x.Value : 0);
result = source.Where(x => x.IsValid).Select(x => x.Value).Sum();

mod moyen: chaque 1 mod des articles n'est pas valide: pour mod == 1 chaque élément n'est pas valide, pour mod == 2 objets bizarres ne sont pas valides, etc. La Collection contient 10000000 articles.

Et les résultats de la collection avec 100000000 articles:

Comme vous pouvez le voir, Select et Sum des résultats sont assez uniformes dans tous mod valeurs. Toutefois where et where+select ne le sont pas.

Answer 4

Ma conjecture est que la version avec Où les filtres les 0s et ils ne sont pas un sujet de Somme (c'est à dire vous n'êtes pas l'exécution de l'addition). Bien sûr, ceci est une supposition car je ne peux pas expliquer comment mettre en place d'autres lambda expression et de l'appel de plusieurs méthodes surpasse un simple ajout d'un 0.

Un ami a suggéré que le fait que le 0 dans la somme peut causer une grave perte de performance en raison de dépassement de contrôles. Il serait intéressant de voir comment cela pourrait effectuer librement contexte.

Answer 5

Exécution de l'exemple suivant, il devient clair pour moi que le seul moment où Select + peut surpasser Select est en fait quand il est en train de jeter une bonne quantité (environ la moitié dans mes tests informels) des éléments potentiels dans la liste. Dans le petit exemple ci-dessous, je reçois à peu près les mêmes nombres sur les deux échantillons lorsque le Where saute environ 4mil sur 10mil. J'ai couru en version, et j'ai réorganisé l'exécution de where + select vs select avec les mêmes résultats.

 static void Main(string[] args)
        {
            int total = 10000000;
            Random r = new Random();
            var list = Enumerable.Range(0, total).Select(i => r.Next(0, 5)).ToList();
            for (int i = 0; i < 4000000; i++)
                list[i] = 10;

            var sw = new Stopwatch();
            sw.Start();

            int sum = 0;

            sum = list.Where(i => i < 10).Select(i => i).Sum();            

            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);

            sw.Reset();
            sw.Start();
            sum = list.Select(i => i).Sum();            

            sw.Stop();

            Console.WriteLine(sw.ElapsedMilliseconds);
        }