Mam taką klasę:

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

_{W rzeczywistości jest znacznie większy, ale to odtwarza problem (dziwność).}

Chcę uzyskać sumę Value, gdzie instancja jest prawidłowa. Jak dotąd znalazłem dwa rozwiązania tego problemu.

Pierwsza z nich to:

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

Drugi to jednak:

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

Chcę uzyskać najbardziej wydajną metodę. Na początku myślałem, że ten drugi będzie bardziej wydajny. Wtedy część teoretyczna mnie zaczęła mówić "No cóż, jedna to O (n + m + m), druga to O (n + n). Pierwsza powinna działać lepiej z większą liczbą inwalidów, a druga powinna działać lepiej mniej ”. Pomyślałem, że będą działać równie dobrze. EDYCJA: A potem @Martin wskazał, że Gdzie i Wybierz zostały połączone, więc powinno to być O (m + n). Jeśli jednak spojrzysz poniżej, wygląda na to, że nie ma to związku.

Więc wystawiłem to na próbę.

_{(To ponad 100 wierszy, więc pomyślałem, że lepiej będzie opublikować to jako streszczenie)}
. Wyniki były ... interesujące.

_{Z 0% tolerancją krawata:}

Skale są na korzyść Selecti Where, o około ~ 30 punktów.

How much do you want to be the disambiguation percentage?
0
Starting benchmarking.
Ties: 0
Where + Select: 65
Select: 36


_{Z 2% tolerancją krawata:}

To jest to samo, z wyjątkiem tego, że dla niektórych były w granicach 2%. Powiedziałbym, że to minimalny margines błędu. Selecta Whereteraz mają tylko ~ 20 punktów przewagi.

How much do you want to be the disambiguation percentage?
2
Starting benchmarking.
Ties: 6
Where + Select: 58
Select: 37


_{Z 5% tolerancją krawata:}

To właśnie powiedziałbym, że jest to mój maksymalny margines błędu. To sprawia, że ​​jest trochę lepiej Select, ale niewiele.

How much do you want to be the disambiguation percentage?
5
Starting benchmarking.
Ties: 17
Where + Select: 53
Select: 31


_{Z 10% tolerancją krawata:}

To jest poza moim marginesem błędu, ale nadal jestem zainteresowany wynikiem. Bo to daje Selecti Wherepunkt dwadzieścia prowadzić to miałem na chwilę teraz.

How much do you want to be the disambiguation percentage?
10
Starting benchmarking.
Ties: 36
Where + Select: 44
Select: 21


_{Z 25% tolerancją krawata:}

To jest sposób, aby wyjść poza mój margines błędu, ale nadal jestem zainteresowany wynikiem, ponieważ Selecti Where nadal (prawie) utrzymują swoją 20-punktową przewagę. Wygląda na to, że deklasuje go w kilku wyraźnych i to właśnie daje mu przewagę.

How much do you want to be the disambiguation percentage?
25
Starting benchmarking.
Ties: 85
Where + Select: 16
Select: 0


Zgaduję, że 20-punktowa przewaga nadeszła ze środka, gdzie obaj będą musieli obejść ten sam występ. Mógłbym spróbować to zarejestrować, ale byłoby to całe mnóstwo informacji do zebrania. Wykres byłby lepszy, jak sądzę.

Więc to właśnie zrobiłem.

Pokazuje, że Selectlinia pozostaje stabilna (oczekiwana) i że Select + Wherelinia wznosi się (oczekiwana). Zastanawiające mnie jednak, dlaczego nie spotyka się z Select50 lub wcześniej: tak naprawdę spodziewałem się wcześniej niż 50, ponieważ trzeba było stworzyć dodatkowy wyliczający dla Selecti Where. To znaczy, to pokazuje 20-punktową przewagę, ale nie wyjaśnia dlaczego. To chyba jest główny punkt mojego pytania.

Dlaczego tak się zachowuje? Powinienem mu ufać? Jeśli nie, powinienem użyć drugiego czy tego?

Jak @KingKong wspomniał w komentarzach, możesz również użyć Sumprzeciążenia, które pobiera lambdę. Więc moje dwie opcje są teraz zmienione na:

Pierwszy:

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

Druga:

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

Mam zamiar to trochę skrócić, ale:

How much do you want to be the disambiguation percentage?
0
Starting benchmarking.
Ties: 0
Where: 60
Sum: 41
How much do you want to be the disambiguation percentage?
2
Starting benchmarking.
Ties: 8
Where: 55
Sum: 38
How much do you want to be the disambiguation percentage?
5
Starting benchmarking.
Ties: 21
Where: 49
Sum: 31
How much do you want to be the disambiguation percentage?
10
Starting benchmarking.
Ties: 39
Where: 41
Sum: 21
How much do you want to be the disambiguation percentage?
25
Starting benchmarking.
Ties: 85
Where: 16
Sum: 0


Dwudziestopunktowa przewaga wciąż istnieje, co oznacza, że ​​nie ma nic wspólnego z kombinacją Wherei Selectwskazaną przez @Marcin w komentarzach.

_{Dziękuję za przeczytanie mojej ściany tekstu! Ponadto, jeśli jesteś zainteresowany, oto zmodyfikowana wersja, która rejestruje plik CSV pobierany przez program Excel.}

Selectwykonuje iterację raz po całym zestawie i dla każdego elementu wykonuje gałąź warunkową (sprawdzanie poprawności) i +operację.

Where+Selecttworzy iterator, który pomija nieprawidłowe elementy (czy nie yield), wykonując +tylko na prawidłowych elementach.

Tak więc koszt za Selectto:

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

I dla Where+Select:

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

Gdzie:

• p(valid) to prawdopodobieństwo, że pozycja na liście jest ważna.
• cost(check valid) jest kosztem oddziału, który sprawdza ważność
• cost(yield)to koszt skonstruowania nowego stanu whereiteratora, który jest bardziej złożony niż prosty iterator Selectużywany w wersji.

Jak widać, dla danej nThe Selectwersja jest na stałym poziomie, podczas gdy Where+Selectwersja jest równanie liniowe z p(valid)jako zmienną. Rzeczywiste wartości kosztów określają punkt przecięcia dwóch linii, a ponieważ cost(yield)mogą być różne od cost(+), niekoniecznie przecinają się przy p(valid)= 0,5.

Oto szczegółowe wyjaśnienie, co powoduje różnice w czasie.

Sum()Funkcja IEnumerable<int>wygląda tak:

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

W C # foreachjest to po prostu cukier składniowy dla iteratora w wersji .Net (nie należy go mylić ) . Więc powyższy kod jest właściwie przetłumaczony na to:IEnumerator<T> IEnumerable<T>

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;
}

Pamiętaj, że porównujesz dwa wiersze kodu

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

Oto kicker:

LINQ używa odroczonego wykonania . Tak więc, chociaż może się wydawać, że result1iteruje po kolekcji dwukrotnie, w rzeczywistości dokonuje iteracji tylko raz. Where()Warunek jest faktycznie stosowane w czasie Sum(), wewnątrz wywołania MoveNext() (Jest to możliwe dzięki magii yield return) .

Oznacza to, że dla result1kodu wewnątrz whilepętli

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

jest wykonywany tylko raz dla każdego elementu z mc.IsValid == true. Dla porównania result2wykona ten kod dla każdego elementu w kolekcji. Dlategoresult1 generalnie jest szybszy.

(Należy jednak pamiętać, że wywołanie Where()warunku w ramach MoveNext()nadal wiąże się z niewielkim narzutem, więc jeśli większość / wszystkie elementy mają mc.IsValid == true, result2będzie faktycznie szybsze!)

Miejmy nadzieję, że teraz jest jasne, dlaczego result2zwykle jest wolniejsze. Teraz chciałbym wyjaśnić, dlaczego podałem to w komentarzach te porównania wydajności LINQ nie mają znaczenia .

Tworzenie wyrażenia LINQ jest tanie. Wywoływanie funkcji delegatów jest tanie. Przydzielanie i zapętlanie iteratora jest tanie. Ale jeszcze taniej jest nie robić tych rzeczy. Tak więc, jeśli okaże się, że instrukcja LINQ jest wąskim gardłem w programie, z mojego doświadczenia wynika, że ​​przepisanie jej bez LINQ spowoduje zawsze sprawi, że będzie ona szybsza niż dowolna z różnych metod LINQ.

Tak więc przepływ pracy LINQ powinien wyglądać następująco:

1. Używaj LINQ wszędzie.
2. Profil.
3. Jeśli profiler mówi, że LINQ jest przyczyną wąskiego gardła, przepisz ten fragment kodu bez LINQ.

Na szczęście wąskie gardła LINQ są rzadkie. Heck, wąskie gardła są rzadkie. Napisałem setki instrukcji LINQ w ciągu ostatnich kilku lat i ostatecznie zastąpiłem <1%. A większość z nich była spowodowana LINQ2EF słabą optymalizacją SQL , a nie winą LINQ.

Tak więc, jak zawsze, najpierw napisz przejrzysty i rozsądny kod i zaczekaj, aż po profilowaniu, aby martwić się o mikro-optymalizacje.

Zabawna rzecz. Czy wiesz, jak Sum(this IEnumerable<TSource> source, Func<TSource, int> selector)zdefiniowano? Używa Selectmetody!

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

Więc właściwie to wszystko powinno działać prawie tak samo. Sam przeprowadziłem szybkie poszukiwania i oto wyniki:

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

Do następujących realizacji:

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();

modoznacza: każda 1 z modpozycji jest nieważna: mod == 1każda pozycja jest nieważna, dla mod == 2pozycji nieparzystych są nieważne itp. Kolekcja zawiera 10000000pozycje.

Wyniki dla kolekcji z 100000000elementami:

Jak widać, Selecti Sumwyniki są dość spójne we wszystkich modwartości. Jednak wherei where+ selectnie.

Domyślam się, że wersja z Where odfiltrowuje 0 i nie są one tematem dla Sum (tj. Nie wykonujesz dodawania). To oczywiście domysł, ponieważ nie potrafię wyjaśnić, w jaki sposób wykonanie dodatkowego wyrażenia lambda i wywołanie wielu metod przewyższa zwykłe dodanie 0.

Mój przyjaciel zasugerował, że fakt, że 0 w sumie może spowodować poważny spadek wydajności z powodu kontroli przepełnienia. Byłoby interesujące zobaczyć, jak będzie to działać w niekontrolowanym kontekście.

Analizując poniższy przykład, staje się dla mnie jasne, że jedyny przypadek, w którym + Select może przewyższać Select, to w rzeczywistości odrzucanie dużej ilości (około połowy w moich nieformalnych testach) potencjalnych pozycji z listy. W małym przykładzie poniżej otrzymuję z grubsza te same liczby z obu próbek, gdy Gdzie pomija około 4 mil z 10 mil. Uruchomiłem w wersji Release i zmieniłem kolejność wykonania where + select vs select z tymi samymi wynikami.

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);
        }

Jeśli potrzebujesz szybkości, prawdopodobnie najlepszym rozwiązaniem będzie wykonanie prostej pętli. A robienie forjest lepsze niż foreach(zakładając oczywiście, że twoja kolekcja jest dostępna losowo).

Oto czasy, które otrzymałem z 10% nieprawidłowych elementów:

Where + Select + Sum:   257
Select + Sum:           253
foreach:                111
for:                    61

A przy 90% nieprawidłowych elementów:

Where + Select + Sum:   177
Select + Sum:           247
foreach:                105
for:                    58

A oto mój kod porównawczy ...

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

class Program {

    static void Main(string[] args) {

        const int count = 10000000;
        const int percentageInvalid = 90;

        var rnd = new Random();
        var myCollection = new List<MyClass>(count);
        for (int i = 0; i < count; ++i) {
            myCollection.Add(
                new MyClass {
                    Value = rnd.Next(0, 50),
                    IsValid = rnd.Next(0, 100) > percentageInvalid
                }
            );
        }

        var sw = new Stopwatch();
        sw.Restart();
        int result1 = myCollection.Where(mc => mc.IsValid).Select(mc => mc.Value).Sum();
        sw.Stop();
        Console.WriteLine("Where + Select + Sum:\t{0}", sw.ElapsedMilliseconds);

        sw.Restart();
        int result2 = myCollection.Select(mc => mc.IsValid ? mc.Value : 0).Sum();
        sw.Stop();
        Console.WriteLine("Select + Sum:\t\t{0}", sw.ElapsedMilliseconds);
        Debug.Assert(result1 == result2);

        sw.Restart();
        int result3 = 0;
        foreach (var mc in myCollection) {
            if (mc.IsValid)
                result3 += mc.Value;
        }
        sw.Stop();
        Console.WriteLine("foreach:\t\t{0}", sw.ElapsedMilliseconds);
        Debug.Assert(result1 == result3);

        sw.Restart();
        int result4 = 0;
        for (int i = 0; i < myCollection.Count; ++i) {
            var mc = myCollection[i];
            if (mc.IsValid)
                result4 += mc.Value;
        }
        sw.Stop();
        Console.WriteLine("for:\t\t\t{0}", sw.ElapsedMilliseconds);
        Debug.Assert(result1 == result4);

    }

}

Przy okazji, zgadzam się z przypuszczeniem Stilgara : względne prędkości w twoich dwóch przypadkach różnią się w zależności od odsetka nieważnych pozycji, po prostu dlatego, że ilość pracy, którą Sumtrzeba wykonać, różni się w przypadku „Gdzie”.

Zamiast próbować wyjaśnić za pomocą opisu, zamierzam przyjąć bardziej matematyczne podejście.

Biorąc pod uwagę poniższy kod, który powinien przybliżać to, co LINQ robi wewnętrznie, koszty względne są następujące:
Wybierz tylko:Nd + Na
Gdzie + Wybierz:Nd + Md + Ma

Aby ustalić punkt, w którym się skrzyżują, musimy zrobić małą algebrę:
Nd + Md + Ma = Nd + Na => M(d + a) = Na => (M/N) = a/(d+a)

Oznacza to, że aby punkt przegięcia miał wartość 50%, koszt wywołania delegata musi być mniej więcej taki sam, jak koszt dodania. Ponieważ wiemy, że rzeczywisty punkt przegięcia wynosił około 60%, możemy pracować wstecz i ustalić, że koszt wywołania delegata dla @ It'sNotALie był w rzeczywistości około 2/3 kosztu dodania, co jest zaskakujące, ale to właśnie mówią jego liczby.

static void Main(string[] args)
{
    var set = Enumerable.Range(1, 10000000)
                        .Select(i => new MyClass {Value = i, IsValid = i%2 == 0})
                        .ToList();

    Func<MyClass, int> select = i => i.IsValid ? i.Value : 0;
    Console.WriteLine(
        Sum(                        // Cost: N additions
            Select(set, select)));  // Cost: N delegate
    // Total cost: N * (delegate + addition) = Nd + Na

    Func<MyClass, bool> where = i => i.IsValid;
    Func<MyClass, int> wSelect = i => i.Value;
    Console.WriteLine(
        Sum(                        // Cost: M additions
            Select(                 // Cost: M delegate
                Where(set, where),  // Cost: N delegate
                wSelect)));
    // Total cost: N * delegate + M * (delegate + addition) = Nd + Md + Ma
}

// Cost: N delegate calls
static IEnumerable<T> Where<T>(IEnumerable<T> set, Func<T, bool> predicate)
{
    foreach (var mc in set)
    {
        if (predicate(mc))
        {
            yield return mc;
        }
    }
}

// Cost: N delegate calls
static IEnumerable<int> Select<T>(IEnumerable<T> set, Func<T, int> selector)
{
    foreach (var mc in set)
    {
        yield return selector(mc);
    }
}

// Cost: N additions
static int Sum(IEnumerable<int> set)
{
    unchecked
    {
        var sum = 0;
        foreach (var i in set)
        {
            sum += i;
        }

        return sum;
    }
}

Myślę, że to ciekawe, że wynik MarcinaJuraszka różni się od wyniku It'sNotALie. W szczególności wyniki Marcina Juraszka zaczynają się od wszystkich czterech wdrożeń w tym samym miejscu, podczas gdy wyniki It'sNotALie przecinają się wokół środka. Wyjaśnię, jak to działa ze źródła.

Załóżmy, że istnieją nwszystkie elementy i mprawidłowe elementy.

SumFunkcja jest dość prosta. Po prostu przechodzi przez moduł wyliczający: http://typedescriptor.net/browse/members/367300-System.Linq.Enumerable.Sum(IEnumerable%601)

Dla uproszczenia załóżmy, że kolekcja jest listą. Zarówno Select, jak i WhereSelect utworzą plik WhereSelectListIterator. Oznacza to, że faktycznie wygenerowane iteratory są takie same. W obu przypadkach istnieje Sumpętla nad iteratorem, czyli WhereSelectListIterator. Najbardziej interesującą częścią iteratora jest MoveNext metoda .

Ponieważ iteratory są takie same, pętle są takie same. Jedyną różnicą jest korpus pętli.

Ciało tych lambd ma bardzo podobny koszt. Klauzula where zwraca wartość pola, a predykat trójskładnikowy również zwraca wartość pola. Klauzula select zwraca wartość pola, a dwie gałęzie operatora trójskładnikowego zwracają wartość pola lub stałą. Połączona klauzula select ma gałąź jako operator trójskładnikowy, ale WhereSelect używa gałęzi w MoveNext.

Jednak wszystkie te operacje są dość tanie. Najdroższą jak dotąd operacją jest branża, w której błędna prognoza będzie nas kosztować.

Inną kosztowną operacją jest tutaj Invoke. Wywołanie funkcji zajmuje trochę więcej czasu niż dodanie wartości, jak pokazał Branko Dimitrijevic.

Ważenie jest również sprawdzaną akumulacją Sum . Jeśli procesor nie ma arytmetycznej flagi przepełnienia, sprawdzenie tego również może być kosztowne.

Stąd interesujące koszty to: to:

1. ( n+ m) * Wywołaj + m*checked+=
2. n* Wywołaj + n*checked+=

Tak więc, jeśli koszt Invoke jest znacznie wyższy niż koszt sprawdzonej akumulacji, wtedy przypadek 2 jest zawsze lepszy. Jeśli są równe, równowagę zobaczymy, gdy około połowa elementów będzie poprawna.

Wygląda na to, że na systemie Marcina Juraszka, zaznaczone + = ma znikomy koszt, ale na systemach It'sNotALie i Branko Dimitrijevic, zaznaczone + = ma spore koszty. Wygląda na to, że jest najdroższy w systemie It'sNotALie, ponieważ próg rentowności jest znacznie wyższy. Nie wygląda na to, aby ktokolwiek opublikował wyniki z systemu, w którym akumulacja kosztuje znacznie więcej niż Invoke.