c# - Rendimiento de Find() vs. FirstOrDefault()

.net performance

Question

Pregunta similar:
Find () frente a Where (). FirstOrDefault ()

Obtuve un resultado interesante al buscar a Diana dentro de una gran secuencia de un tipo de referencia simple que tiene una sola propiedad de cadena.

using System;
using System.Collections.Generic;
using System.Linq;

public class Customer{
    public string Name {get;set;}
}

Stopwatch watch = new Stopwatch();        
    const string diana = "Diana";

    while (Console.ReadKey().Key != ConsoleKey.Escape)
    {
        //Armour with 1000k++ customers. Wow, should be a product with a great success! :)
        var customers = (from i in Enumerable.Range(0, 1000000)
                         select new Customer
                         {
                            Name = Guid.NewGuid().ToString()
                         }).ToList();

        customers.Insert(999000, new Customer { Name = diana }); // Putting Diana at the end :)

        //1. System.Linq.Enumerable.DefaultOrFirst()
        watch.Restart();
        customers.FirstOrDefault(c => c.Name == diana);
        watch.Stop();
        Console.WriteLine("Diana was found in {0} ms with System.Linq.Enumerable.FirstOrDefault().", watch.ElapsedMilliseconds);

        //2. System.Collections.Generic.List<T>.Find()
        watch.Restart();
        customers.Find(c => c.Name == diana);
        watch.Stop();
        Console.WriteLine("Diana was found in {0} ms with System.Collections.Generic.List<T>.Find().", watch.ElapsedMilliseconds);
    }

¿Esto se debe a que no hay sobrecarga del Enumerador en List.Find () o esto más, tal vez algo más?

Find() funciona casi dos veces más rápido, con la esperanza de que el equipo .Net no lo marque Obsoleto en el futuro.

Answer 1

Estoy apostando a que FirstOrDefault se ejecuta a través de la implementación de IEnumerable , es decir, usará un ciclo foreach estándar para hacer la verificación. List<T>.Find() no es parte de Linq ( http://msdn.microsoft.com/en-us/library/x0b5b5bc.aspx ), y es probable que utilice un estándar for ciclo de 0 a Count (u otro mecanismo interno rápido probablemente operando directamente en su matriz interna / envuelta). Al deshacerse de la sobrecarga de enumerar (y hacer las verificaciones de versión para asegurarse de que la lista no se haya modificado), el método Find es más rápido.

Si agrega una tercera prueba:

//3. System.Collections.Generic.List<T> foreach
Func<Customer, bool> dianaCheck = c => c.Name == diana;
watch.Restart();
foreach(var c in customers)
{
    if (dianaCheck(c))
        break;
}
watch.Stop();
Console.WriteLine("Diana was found in {0} ms with System.Collections.Generic.List<T> foreach.", watch.ElapsedMilliseconds);

Eso corre aproximadamente la misma velocidad que el primero (25ms vs 27ms para FirstOrDefault )

EDITAR: Si agrego un bucle de matriz, se acerca bastante a la velocidad de Find() , y dado que @devshorts eche un vistazo al código fuente, creo que es esto:

//4. System.Collections.Generic.List<T> for loop
var customersArray = customers.ToArray();
watch.Restart();
int customersCount = customersArray.Length;
for (int i = 0; i < customersCount; i++)
{
    if (dianaCheck(customers[i]))
        break;
}
watch.Stop();
Console.WriteLine("Diana was found in {0} ms with an array for loop.", watch.ElapsedMilliseconds);

Esto solo funciona un 5.5% más lento que el método Find() .

Entonces, línea de fondo: el bucle a través de los elementos de la matriz es más rápido que lidiar con la sobrecarga de iteración foreach . (pero ambos tienen sus pros / contras, así que simplemente elija lo que tenga sentido para su código lógicamente. Además, solo pocas veces la pequeña diferencia de velocidad causará problemas, así que simplemente use lo que tenga sentido para la facilidad de mantenimiento / legibilidad)

Answer 2

Pude imitar tus resultados, así que descompilé tu programa y existe una diferencia entre Find y FirstOrDefault .

Primero aquí está el programa descompilado. Hice su objeto de datos un elemento de datos anónimos para compilación

    List</u003C/u003Ef__AnonymousType0<string>> source = Enumerable.ToList(Enumerable.Select(Enumerable.Range(0, 1000000), i =>
    {
      var local_0 = new
      {
        Name = Guid.NewGuid().ToString()
      };
      return local_0;
    }));
    source.Insert(999000, new
    {
      Name = diana
    });
    stopwatch.Restart();
    Enumerable.FirstOrDefault(source, c => c.Name == diana);
    stopwatch.Stop();
    Console.WriteLine("Diana was found in {0} ms with System.Linq.Enumerable.FirstOrDefault().", (object) stopwatch.ElapsedMilliseconds);
    stopwatch.Restart();
    source.Find(c => c.Name == diana);
    stopwatch.Stop();
    Console.WriteLine("Diana was found in {0} ms with System.Collections.Generic.List<T>.Find().", (object) stopwatch.ElapsedMilliseconds);

La clave a tener en cuenta aquí es que FirstOrDefault se llama en Enumerable mientras que Find se llama como método en la lista de origen.

Entonces, ¿qué es encontrar haciendo? Este es el método Find descompilado

private T[] _items;

[__DynamicallyInvokable]
public T Find(Predicate<T> match)
{
  if (match == null)
    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  for (int index = 0; index < this._size; ++index)
  {
    if (match(this._items[index]))
      return this._items[index];
  }
  return default (T);
}

Por lo tanto, iterar sobre una matriz de elementos tiene sentido, ya que una lista es un contenedor de una matriz.

Sin embargo, FirstOrDefault , en la clase Enumerable , usa foreach para iterar los elementos. Esto usa un iterador en la lista y se mueve a continuación. Creo que lo que estás viendo es la sobrecarga del iterador

[__DynamicallyInvokable]
public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
  if (source == null)
    throw Error.ArgumentNull("source");
  if (predicate == null)
    throw Error.ArgumentNull("predicate");
  foreach (TSource source1 in source)
  {
    if (predicate(source1))
      return source1;
  }
  return default (TSource);
}

Foreach es solo azúcar sintáctico al usar el patrón enumerable. Mira esta imagen

.

Hice clic en Foreach para ver qué está haciendo y se puede ver que dotpeek quiere llevarme a las implementaciones del enumerador / actual / siguiente, lo cual tiene sentido.

Aparte de eso, son básicamente los mismos (probar el predicado pasado para ver si un artículo es lo que quieres)