.Max() vs OrderByDescending(). First()

Question

Это чисто для моих собственных знаний, если бы я собирался написать код, я бы просто использовал .Max().

Сперва подумал, что .Max() должен выполнить только один проход через numbers, чтобы найти максимальное значение, в то время как второй способ должен отсортировать всю перечислимую вещь, а затем найти первую. Так что это O(n) vs O(n lg n). Но потом я подумал, может быть, он знает, что ему нужно только самое высокое и просто хватает его.

Вопрос: Является LINQ и/или компилятор достаточно умен, чтобы понять, что это не нужно сортировать всю перечислимы и кипятит код вниз, по существу, такой же, как .MAX()? Есть ли способ поддаваться количественному определению?

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

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

Answer 1

Если вы говорите о прямой LINQ к объектам, то нет, это не оптимизирует для этого.

Предположительно, возможно, другой поставщик LINQ, но это зависит от особенностей реализации.

Для перечислимых, реализации, что отражатель дает мне это:

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

и 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() О (п), в то время как ваше решение OrderByDescending нет - в зависимости от вида, вероятно, это O (Nlog (п)).

Я, очевидно, не выкопал внутри компилятора, чтобы узнать, но то, что вы просите (оптимизация, которая реализует сортировку, а затем захватить только один элемент, такая же, как и .max), довольно много от компилятора.

Answer 3

Является LINQ и/или компилятор достаточно умен, чтобы понять, что это не нужно отсортировать весь перечислимый и закипеть код до по существу того же самого, что и .Max()?

No.

Есть ли количественный способ узнать?

простой тест с Секундомер:

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

Макс(): 70ms

OrderBy(): 2066ms

Кроме того, OrderBy() терпит неудачу с OutOfMemoryException если увеличить количество слишком много за этим, Макс() не делает этого.

Answer 4

Похоже, что OrderedEnumerable теперь достаточно умен, чтобы понять, что ему не нужно сортировать список для First и Last().

Обратите внимание на код в пределах линии 223, TryGetFirst() https://github.com/dotnet/corefx/blob/ed0ee133ac49cee86f10ca4692b1d72e337bc012/src/System.Linq/src/System/Linq/OrderedEnumerable.cs