.Max() vs OrderByDescending(). Primero()

Question

Esto es puramente para mi propio conocimiento, si fuera a escribir el código solo usaría .Max().

Al principio, .Max() solo tiene que hacer un pase simple a través de numbers para encontrar el máximo, mientras que la segunda forma tiene que ordenar todo lo enumerable y luego encontrar el primero. Entonces es O(n) vs O(n lg n). Pero luego pensé que tal vez sabía que solo necesitaba lo mejor y solo lo agarraba.

Pregunta: ¿Es LINQ y/o el compilador lo suficientemente inteligente como para saber que no hay que solucionar todo el enumerables y hierve el código de abajo a esencialmente el mismo que .MAX()? ¿Hay alguna forma cuantificable de averiguarlo?

IEnumerable<int> numbers = Enumerable.Range(1, 1000); 

int max = numbers.Max(); 
int max2 = numbers.OrderByDescending(x => x).First(); 

Answer 1

Si está hablando directamente de LINQ to Objects, entonces no, no optimiza para eso.

Posiblemente otro proveedor de LINQ podría hacerlo, pero eso depende de los detalles de la implementación.

Para Enumerable, las implementaciones que Reflector me da son:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) 
{ 
    return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false); 
} 

y para First()

public static TSource First<TSource>(this IEnumerable<TSource> source) 
{ 
    if (source == null) 
    { 
     throw Error.ArgumentNull("source"); 
    } 
    IList<TSource> list = source as IList<TSource>; 
    if (list != null) 
    { 
     if (list.Count > 0) 
     { 
      return list[0]; 
     } 
    } 
    else 
    { 
     using (IEnumerator<TSource> enumerator = source.GetEnumerator()) 
     { 
      if (enumerator.MoveNext()) 
      { 
       return enumerator.Current; 
      } 
     } 
    } 
    throw Error.NoElements(); 
} 

Answer 2

.Max() es O (n), mientras que su solución no es OrderByDescending - dependiendo de la especie, es probable que sea O (n log (n)).

Obviamente no he profundizado en el compilador para saberlo, pero lo que estás pidiendo (una optimización que se realiza ordena y luego agarra solo un elemento es lo mismo que .max) es bastante de un compilador.

Answer 3

Es LINQ y/o el compilador lo suficientemente inteligente como para saber que no es así necesita ordenar todo el enumerable y reduce el código a esencialmente igual que .Max()?

Nº

¿Hay una manera cuantificable para averiguar?

una referencia sencilla con el cronómetro:

var numbers = Enumerable.Range(1, 10000000); 
    var sw = Stopwatch.StartNew(); 
    int max = numbers.Max(); 
    Console.WriteLine(sw.ElapsedMilliseconds); 
    sw.Restart(); 
    int max2 = numbers.OrderByDescending(x => x).First(); 
    Console.WriteLine(sw.ElapsedMilliseconds); 

Max(): 70 ms

OrdenarPor(): 2066ms

Además, OrdenarPor() falla con un OutOfMemoryException si se aumenta el recuento demasiado más allá de eso, Max() no.

Answer 4

Parece que OrderedEnumerable ahora es lo suficientemente inteligente como para darse cuenta de que no necesita ordenar la lista para Primero y Último().

Nota el código en torno a la línea 223, TryGetFirst() https://github.com/dotnet/corefx/blob/ed0ee133ac49cee86f10ca4692b1d72e337bc012/src/System.Linq/src/System/Linq/OrderedEnumerable.cs