Eu tenho uma classe, assim:

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

_{Na verdade, é muito maior, mas isso recria o problema (esquisitice).}

Eu quero obter a soma do Value, onde a instância é válida. Até agora, encontrei duas soluções para isso.

O primeiro é o seguinte:

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

O segundo, no entanto, é o seguinte:

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

Eu quero obter o método mais eficiente. A princípio, pensei que o segundo seria mais eficiente. Então a parte teórica de mim começou a dizer "Bem, um é O (n + m + m), o outro é O (n + n). O primeiro deve ter um desempenho melhor com mais inválidos, enquanto o segundo deve ter um desempenho melhor com menos". Eu pensei que eles teriam um desempenho igual. EDIT: E então @Martin apontou que o Where e o Select foram combinados, portanto deve ser O (m + n). No entanto, se você olhar abaixo, parece que isso não está relacionado.

Então eu testei.

_{(São mais de 100 linhas, então pensei que era melhor publicá-lo como um Gist.)}
Os resultados foram ... interessantes.

_{Com tolerância de empate de 0%:}

As escalas são a favor Selecte Where, em cerca de ~ 30 pontos.

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


_{Com 2% de tolerância de empate:}

É o mesmo, exceto que para alguns eles estavam dentro de 2%. Eu diria que é uma margem mínima de erro. Selecte Whereagora tem apenas uma vantagem de ~ 20 pontos.

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


_{Com 5% de tolerância de empate:}

Isso é o que eu diria ser a minha margem máxima de erro. Isso torna um pouco melhor para o Select, mas não muito.

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


_{Com 10% de tolerância de empate:}

Isso está fora da minha margem de erro, mas ainda estou interessado no resultado. Porque dá a Selecte Wherea vantagem de vinte pontos que já há algum tempo.

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


_{Com 25% de tolerância de empate:}

Esta é a maneira, maneira fora da minha margem de erro, mas eu ainda estou interessado no resultado, porque o Selecte Where ainda (quase) manter sua vantagem de 20 pontos. Parece que ele está superando em poucos, e é isso que está dando a liderança.

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


Agora, eu estou supondo que a liderança de 20 pontos veio do meio, onde ambos são obrigados a ficar em torno do mesmo desempenho. Eu poderia tentar registrá-lo, mas seria uma carga de informações para absorver. Um gráfico seria melhor, eu acho.

Então foi o que eu fiz.

Isso mostra que a Selectlinha se mantém estável (esperada) e que a Select + Wherelinha sobe (esperada). No entanto, o que me intriga é o motivo pelo qual ele não se encontra com os Select50 ou mais anteriores: na verdade, eu esperava mais de 50, pois um enumerador extra precisava ser criado para o Selecte Where. Quero dizer, isso mostra a vantagem de 20 pontos, mas não explica o porquê. Acho que esse é o ponto principal da minha pergunta.

Por que se comporta assim? Devo confiar nisso? Caso contrário, devo usar o outro ou este?

Como o @KingKong mencionado nos comentários, você também pode usar Suma sobrecarga de uma lambda. Então, minhas duas opções agora foram alteradas para isso:

Primeiro:

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

Segundo:

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

Vou torná-lo um pouco mais curto, mas:

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


A liderança de vinte pontos ainda está lá, o que significa que não tem a ver com a combinação Wheree Selectapontada por @Marcin nos comentários.

_{Obrigado por ler minha parede de texto! Além disso, se você estiver interessado, aqui está a versão modificada que registra o CSV que o Excel recebe.}

Selectitera uma vez em todo o conjunto e, para cada item, executa uma ramificação condicional (verificação de validade) e uma +operação.

Where+Selectcria um iterador que ignora elementos inválidos (não yieldos faz), executando +apenas os itens válidos.

Portanto, o custo para a Selecté:

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

E para Where+Select:

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

Onde:

• p(valid) é a probabilidade de um item da lista ser válido.
• cost(check valid) é o custo da filial que verifica a validade
• cost(yield)é o custo de construção do novo estado do whereiterador, que é mais complexo que o iterador simples que a Selectversão usa.

Como você pode ver, na Selectversão é uma constante, enquanto a Where+Selectversão é uma equação linear com p(valid)uma variável. Os valores reais dos custos determinam o ponto de interseção das duas linhas e, como cost(yield)podem ser diferentes cost(+), eles não necessariamente se cruzam em p(valid)= 0,5.

Aqui está uma explicação detalhada do que está causando as diferenças de tempo.

A Sum()função para se IEnumerable<int>parece com isso:

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

Em C #, foreaché apenas o açúcar sintático para a versão de iterador da .Net (não deve ser confundida com ) . Portanto, o código acima é realmente traduzido para isso: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;
}

Lembre-se, as duas linhas de código que você está comparando são as seguintes

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

Agora aqui está o kicker:

O LINQ usa execução adiada . Portanto, embora pareça que result1itera sobre a coleção duas vezes, na verdade, apenas itera uma vez. A Where()condição é realmente aplicada durante Sum(), dentro da chamada para MoveNext() (Isso é possível graças à magia de yield return) .

Isso significa que, para result1, o código dentro do whileloop,

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

é executado apenas uma vez para cada item com mc.IsValid == true. Por comparação, result2executará esse código para todos os itens da coleção. É por isso que result1geralmente é mais rápido.

(No entanto, observe que chamar a Where()condição dentro MoveNext()ainda tem uma pequena sobrecarga, portanto, se a maioria / todos os itens tiver mc.IsValid == true, result2será realmente mais rápido!)

Espero que agora esteja claro por que result2geralmente é mais lento. Agora, gostaria de explicar por que afirmei nos comentários que essas comparações de desempenho do LINQ não importam .

Criar uma expressão LINQ é barato. Chamar funções de delegado é barato. Alocar e fazer um loop sobre um iterador é barato. Mas é ainda mais barato não fazer essas coisas. Portanto, se você achar que uma instrução LINQ é o gargalo no seu programa, na minha experiência, reescrevê-la sem o LINQ sempre o tornará mais rápido do que qualquer um dos vários métodos LINQ.

Portanto, seu fluxo de trabalho LINQ deve ficar assim:

1. Use o LINQ em qualquer lugar.
2. Perfil.
3. Se o criador de perfil disser que o LINQ é a causa de um gargalo, reescreva esse trecho de código sem o LINQ.

Felizmente, os gargalos do LINQ são raros. Parreira, gargalos são raros. Escrevi centenas de instruções LINQ nos últimos anos e acabei substituindo <1%. E a maioria deles ocorreu devido à fraca otimização de SQL do LINQ2EF , em vez de ser culpa do LINQ.

Portanto, como sempre, escreva primeiro um código claro e sensível e espere até depois de criar um perfil para se preocupar com as otimizações.

Coisa engraçada. Você sabe como é Sum(this IEnumerable<TSource> source, Func<TSource, int> selector)definido? Ele usa Selectmétodo!

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

Então, na verdade, tudo deve funcionar quase da mesma forma. Eu fiz uma pesquisa rápida por conta própria, e aqui estão os resultados:

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

Para as seguintes implementações:

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

modsignifica: todos os 1 moditens são inválidos: mod == 1todos os itens são inválidos, mod == 2os itens ímpares são inválidos etc. A coleção contém 10000000itens.

E resultados para coleta com 100000000itens:

Como você pode ver, Selecte Sumos resultados são bastante consistentes em todos os modvalores. No entanto wheree where+ selectnão são.

Meu palpite é que a versão com Where filtra os 0s e eles não são um assunto para Sum (ou seja, você não está executando a adição). Obviamente, isso é um palpite, já que não posso explicar como a execução de expressões lambda adicionais e a chamada de vários métodos superam uma simples adição de um 0.

Um amigo meu sugeriu que o fato de o 0 na soma possa causar uma severa penalidade de desempenho devido a verificações de estouro. Seria interessante ver como isso funcionaria em um contexto não verificado.

Executando o exemplo a seguir, fica claro para mim que o único momento em que o Where + Select pode superar o Select é de fato quando ele descarta uma boa quantidade (aproximadamente metade dos meus testes informais) dos itens em potencial na lista. No pequeno exemplo abaixo, recebo aproximadamente os mesmos números de ambas as amostras quando o Where ignora aproximadamente 4mil itens de 10mil. Corri na versão e reordenou a execução de where + select vs select com os mesmos resultados.

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

Se você precisar de velocidade, apenas fazer um loop direto é provavelmente a sua melhor aposta. E fazer fortende a ser melhor do que foreach(supondo que sua coleção seja de acesso aleatório, é claro).

Aqui estão os horários que recebi com 10% dos elementos inválidos:

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

E com 90% de elementos inválidos:

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

E aqui está o meu código de referência ...

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

    }

}

Aliás, concordo com o palpite de Stilgar : as velocidades relativas dos seus dois casos variam dependendo da porcentagem de itens inválidos, simplesmente porque a quantidade de trabalho que Sumprecisa ser feita varia no caso "Onde".

Em vez de tentar explicar por descrição, vou adotar uma abordagem mais matemática.

Dado o código abaixo, que deve aproximar o que o LINQ está fazendo internamente, os custos relativos são os seguintes:
Selecione apenas: Nd + Na
Onde + Selecione:Nd + Md + Ma

Para descobrir o ponto em que eles cruzarão, precisamos fazer uma pequena álgebra:
Nd + Md + Ma = Nd + Na => M(d + a) = Na => (M/N) = a/(d+a)

O que isso significa é que, para que o ponto de inflexão esteja em 50%, o custo de uma chamada de delegado deve ser aproximadamente o mesmo que o custo de uma adição. Como sabemos que o ponto de inflexão real era de cerca de 60%, podemos trabalhar para trás e determinar que o custo de uma chamada de delegado para @ It'sNotALie era na verdade cerca de 2/3 do custo de uma adição que é surpreendente, mas é isso que dizem seus números.

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

Acho interessante que o resultado de MarcinJuraszek seja diferente do de It'sNotALie. Em particular, os resultados de MarcinJuraszek começam com todas as quatro implementações no mesmo local, enquanto os resultados de It'sNotALie se cruzam no meio. Vou explicar como isso funciona a partir da fonte.

Vamos assumir que existem nelementos totais e melementos válidos.

A Sumfunção é bem simples. Ele apenas percorre o enumerador: http://typedescriptor.net/browse/members/367300-System.Linq.Enumerable.Sum(IEnumerable%601)

Para simplificar, vamos assumir que a coleção é uma lista. Tanto o Select quanto o WhereSelect criarão um WhereSelectListIterator. Isso significa que os iteradores reais gerados são os mesmos. Nos dois casos, existe um Sumloop que passa por um iterador, o WhereSelectListIterator. A parte mais interessante do iterador é o método MoveNext .

Como os iteradores são iguais, os loops são os mesmos. A única diferença está no corpo dos loops.

O corpo dessas lambdas tem um custo muito semelhante. A cláusula where retorna um valor de campo e o predicado ternário também retorna um valor de campo. A cláusula select retorna um valor de campo e as duas ramificações do operador ternário retornam um valor de campo ou uma constante. A cláusula select combinada tem o ramo como um operador ternário, mas o WhereSelect utiliza o ramo em MoveNext.

No entanto, todas essas operações são bastante baratas. A operação mais cara até agora é a filial, onde uma previsão errada nos custará.

Outra operação cara aqui é a Invoke. A chamada de uma função demora um pouco mais do que a adição de um valor, como mostrou o Branko Dimitrijevic.

Também pesando é a acumulação verificada Sum. Se o processador não tiver um sinalizador de estouro aritmético, também pode ser caro verificar isso.

Portanto, os custos interessantes são: é:

1. ( n+ m) * Invocar + m*checked+=
2. n* Invocar + n*checked+=

Portanto, se o custo de Invoke for muito maior que o custo da acumulação verificada, o caso 2 será sempre melhor. Se eles são iguais, veremos um equilíbrio quando cerca de metade dos elementos forem válidos.

Parece que no sistema de MarcinJuraszek, marcado + = tem custo insignificante, mas nos sistemas de It'sNotALie e Branko Dimitrijevic, marcado + = tem custos significativos. Parece que é o mais caro do sistema It'sNotALie, já que o ponto de equilíbrio é muito maior. Parece que ninguém postou resultados de um sistema em que a acumulação custa muito mais que o Invoke.