Tengo una clase como esta:

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

_{De hecho, es mucho más grande, pero esto recrea el problema (rareza).}

Quiero obtener la suma de Value, donde la instancia es válida. Hasta ahora, he encontrado dos soluciones para esto.

El primero es este:

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

La segunda, sin embargo, es esta:

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

Quiero obtener el método más eficiente. Al principio, pensé que el segundo sería más eficiente. Entonces la parte teórica de mí comenzó a decir "Bueno, uno es O (n + m + m), el otro es O (n + n). El primero debería funcionar mejor con más inválidos, mientras que el segundo debería funcionar mejor con menos". Pensé que actuarían por igual. EDITAR: Y luego @Martin señaló que el Dónde y el Seleccionar se combinaron, por lo que en realidad debería ser O (m + n). Sin embargo, si mira a continuación, parece que esto no está relacionado.

Así que lo puse a prueba.

_{(Son más de 100 líneas, así que pensé que era mejor publicarlo como un Gist.)}
Los resultados fueron ... interesantes.

_{Con 0% de tolerancia de empate:}

Las escalas están a favor de Selecty Where, en aproximadamente ~ 30 puntos.

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


_{Con 2% de tolerancia de empate:}

Es lo mismo, excepto que para algunos estaban dentro del 2%. Yo diría que es un margen mínimo de error. Selecty Whereahora solo tengo una ventaja de ~ 20 puntos.

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


_{Con 5% de tolerancia de empate:}

Esto es lo que yo diría que es mi margen de error máximo. Lo hace un poco mejor para el Select, pero no mucho.

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


_{Con 10% de tolerancia de empate:}

Esto está fuera de mi margen de error, pero todavía estoy interesado en el resultado. Porque da la Selecty Whereel punto de veinte conducir que ha tenido desde hace un tiempo.

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


_{Con 25% de tolerancia de empate:}

Esto está muy, muy lejos de mi margen de error, pero todavía estoy interesado en el resultado, porque todavíaSelect y (casi) mantienen su ventaja de 20 puntos. Parece que lo está superando en unos pocos, y eso es lo que le da el liderazgo.Where

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


Ahora, supongo que la ventaja de 20 puntos venía del medio, donde los dos están obligados a obtener alrededor la misma actuación. Podría intentar registrarlo, pero sería una gran cantidad de información para asimilar. Supongo que un gráfico sería mejor.

Entonces eso fue lo que hice.

Muestra que la Selectlínea se mantiene estable (esperada) y que la Select + Wherelínea sube (esperada). Sin embargo, lo que me desconcierta es por qué no cumple con los Select50 o antes: de hecho, esperaba antes de los 50, ya que se tenía que crear un enumerador adicional para el SelectyWhere . Quiero decir, esto muestra la ventaja de 20 puntos, pero no explica por qué. Este, supongo, es el punto principal de mi pregunta.

¿Por qué se comporta así? ¿Debo confiar en eso? Si no, ¿debería usar el otro o este?

Como @KingKong mencionó en los comentarios, también puede usar Sum la sobrecarga de un lambda. Entonces mis dos opciones ahora se cambian a esto:

Primero:

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

Segundo:

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

Lo haré un poco más corto, pero:

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


La ventaja de veinte puntos sigue ahí, lo que significa que no tiene que ver con el WhereySelect combinación combinación señalada por @Marcin en los comentarios.

_{¡Gracias por leer mi muro de texto! Además, si está interesado, aquí está la versión modificada que registra el CSV que toma Excel.}

Selectitera una vez sobre todo el conjunto y, para cada elemento, realiza una rama condicional (comprobación de validez) y una +operación.

Where+Selectcrea un iterador que omite elementos no válidos (no yieldlos hace), realizando un +solo en los elementos válidos.

Entonces, el costo de a Selectes:

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

Y para Where+Select:

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

Dónde:

• p(valid) es la probabilidad de que un elemento de la lista sea válido.
• cost(check valid) es el costo de la sucursal que verifica la validez
• cost(yield)es el costo de construir el nuevo estado del whereiterador, que es más complejo que el simple iterador que Selectusa la versión.

Como puede ver, para una versión dada n, la Selectversión es una constante, mientras que la Where+Selectversión es una ecuación lineal con p(valid)una variable. Los valores reales de los costos determinan el punto de intersección de las dos líneas y, dado que cost(yield)pueden ser diferentes cost(+), no necesariamente se intersecan en p(valid)= 0.5.

Aquí hay una explicación en profundidad de lo que está causando las diferencias de tiempo.

La Sum()función para se IEnumerable<int>ve así:

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

En C #, foreaches solo azúcar sintáctico para la versión de .Net de un iterador, (no debe confundirse con ) . Entonces, el código anterior se traduce realmente a esto: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;
}

Recuerde, las dos líneas de código que está comparando son las siguientes

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

Ahora aquí está el pateador:

LINQ utiliza ejecución diferida . Por lo tanto, si bien puede parecer que result1itera sobre la colección dos veces, en realidad solo itera sobre ella una vez. La Where()condición se aplica realmente durante Sum(), dentro de la llamada a MoveNext() (Esto es posible gracias a la magia de yield return) .

Esto significa que, para result1, el código dentro del whilebucle,

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

solo se ejecuta una vez por cada elemento con mc.IsValid == true. En comparación, result2ejecutará ese código para cada artículo de la colección. Es por eso queresult1 es generalmente más rápido.

(Sin embargo, tenga en cuenta que llamar a la Where()condición dentro MoveNext()todavía tiene algunos gastos generales pequeños, por lo que si la mayoría / todos los elementos lo tienen mc.IsValid == true, ¡en result2realidad será más rápido!)

Esperemos que ahora esté claro por qué result2suele ser más lento. Ahora me gustaría explicar por qué dije en los comentarios que estas comparaciones de rendimiento de LINQ no importan .

Crear una expresión LINQ es barato. Llamar a las funciones de delegado es barato. Asignar y recorrer un iterador es barato. Pero es aún más barato no hacer estas cosas. Por lo tanto, si encuentra que una declaración LINQ es el cuello de botella en su programa, en mi experiencia, reescribirla sin LINQ siempre la hará más rápida que cualquiera de los diversos métodos LINQ.

Entonces, su flujo de trabajo LINQ debería verse así:

1. Use LINQ en todas partes.
2. Perfil.
3. Si el generador de perfiles dice que LINQ es la causa de un cuello de botella, vuelva a escribir ese código sin LINQ.

Afortunadamente, los cuellos de botella de LINQ son raros. Diablos, los cuellos de botella son raros. He escrito cientos de declaraciones LINQ en los últimos años, y he terminado reemplazando <1%. Y la mayoría de ellos se debieron a LINQ2EF la pobre optimización de SQL de , en lugar de ser culpa de LINQ.

Entonces, como siempre, escriba primero un código claro y sensato, y espere hasta después de que se haya perfilado para preocuparse por las micro optimizaciones.

Cosa graciosa. ¿Sabes cómo se Sum(this IEnumerable<TSource> source, Func<TSource, int> selector)define? ¡Utiliza el Selectmétodo!

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

Entonces, en realidad, todo debería funcionar casi igual. Hice una investigación rápida por mi cuenta, y aquí están los 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 las siguientes implementaciones:

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: cada 1 de los modelementos no es válido: para mod == 1cada elemento no es válido, para mod == 2los elementos impares no son válidos, etc. La colección contiene 10000000elementos.

Y resultados para la colección con 100000000artículos:

Como se puede ver, Selecty Sumlos resultados son bastante consistente a través de todos los modvalores. Sin embargo wherey where+ selectno lo son.

Supongo que la versión con Where filtra los ceros y no son un tema para Sum (es decir, no está ejecutando la adición). Por supuesto, esto es una suposición, ya que no puedo explicar cómo ejecutar una expresión lambda adicional y llamar a varios métodos supera a una simple adición de un 0.

Un amigo mío sugirió que el hecho de que el 0 en la suma pueda causar una severa penalización de rendimiento debido a las comprobaciones de desbordamiento. Sería interesante ver cómo funcionaría esto en un contexto no verificado.

Al ejecutar la siguiente muestra, me queda claro que el único momento en que + Select puede superar a Select es, de hecho, cuando descarta una buena cantidad (aproximadamente la mitad en mis pruebas informales) de los posibles elementos de la lista. En el pequeño ejemplo a continuación, obtengo aproximadamente los mismos números de ambas muestras cuando el Where omite aproximadamente 4mil artículos de 10mil. Corrí en el lanzamiento y reordené la ejecución de where + select vs select con los mismos 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);
        }

Si necesita velocidad, simplemente hacer un bucle directo es probablemente su mejor opción. Y hacerlo fortiende a ser mejor que foreach(suponiendo que su colección sea de acceso aleatorio, por supuesto).

Aquí están los tiempos que obtuve con un 10% de elementos que no son válidos:

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

Y con 90% de elementos inválidos:

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

Y aquí está mi código de referencia ...

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

    }

}

Por cierto, estoy de acuerdo con la suposición de Stilgar : las velocidades relativas de sus dos casos varían según el porcentaje de elementos no válidos, simplemente porque la cantidad de trabajo que Sumdebe hacer varía en el caso "Dónde".

En lugar de tratar de explicar a través de la descripción, voy a adoptar un enfoque más matemático.

Dado el siguiente código que debe aproximarse a lo que LINQ está haciendo internamente, los costos relativos son los siguientes:
Seleccione solo:Nd + Na
Donde + Seleccionar:Nd + Md + Ma

Para descubrir el punto donde se cruzarán, necesitamos hacer un poco de álgebra:
Nd + Md + Ma = Nd + Na => M(d + a) = Na => (M/N) = a/(d+a)

Lo que esto significa es que para que el punto de inflexión sea del 50%, el costo de una invocación de delegado debe ser aproximadamente el mismo que el costo de una adición. Como sabemos que el punto de inflexión real era de aproximadamente el 60%, podemos trabajar hacia atrás y determinar que el costo de una invocación de delegado para @ It'sNotALie era en realidad aproximadamente 2/3 del costo de una adición, lo cual es sorprendente, pero eso es lo que dicen sus 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;
    }
}

Creo que es interesante que el resultado de MarcinJuraszek sea diferente del de It'sNotALie. En particular, los resultados de MarcinJuraszek comienzan con las cuatro implementaciones en el mismo lugar, mientras que los resultados de It'sNotALie se cruzan por la mitad. Explicaré cómo funciona esto desde la fuente.

Supongamos que hay nelementos totales, ym elementos válidos.

La Sumfunción es bastante simple. Simplemente recorre el enumerador: http://typedescriptor.net/browse/members/367300-System.Linq.Enumerable.Sum(IEnumerable%601)

Por simplicidad, supongamos que la colección es una lista. Tanto Select como WhereSelect crearán a WhereSelectListIterator. Esto significa que los iteradores reales generados son los mismos. En ambos casos, hay un Sumque recorre un iterador, el WhereSelectListIterator. La parte más interesante del iterador es el método MoveNext .

Como los iteradores son iguales, los bucles son iguales. La única diferencia está en el cuerpo de los bucles.

El cuerpo de estas lambdas tiene un costo muy similar. La cláusula where devuelve un valor de campo, y el predicado ternario también devuelve un valor de campo. La cláusula select devuelve un valor de campo, y las dos ramas del operador ternario devuelven un valor de campo o una constante. La cláusula select combinada tiene la rama como operador ternario, pero WhereSelect usa la rama enMoveNext .

Sin embargo, todas estas operaciones son bastante baratas. La operación más cara hasta ahora es la sucursal, donde nos costará una predicción incorrecta.

Otra operación costosa aquí es la Invoke . Invocar una función lleva bastante más tiempo que agregar un valor, como ha demostrado Branko Dimitrijevic.

También se pesa la acumulación comprobada en Sum . Si el procesador no tiene un indicador de desbordamiento aritmético, entonces también podría ser costoso verificarlo.

Por lo tanto, los costos interesantes son: es:

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

Por lo tanto, si el costo de Invoke es mucho más alto que el costo de la acumulación controlada, entonces el caso 2 siempre es mejor. Si son casi iguales, entonces veremos un equilibrio cuando aproximadamente la mitad de los elementos sean válidos.

Parece que en el sistema de MarcinJuraszek, marcado + = tiene un costo insignificante, pero en los sistemas de It'sNotALie y Branko Dimitrijevic, marcado + = tiene costos significativos. Parece que es el más caro en el sistema It'sNotALie ya que el punto de equilibrio es mucho mayor. No parece que nadie haya publicado resultados de un sistema donde la acumulación cuesta mucho más que la invocación.