.Max（）vs OrderByDescending（）。First（）

Question

私がコードを書くつもりならば、これは純粋に私自身の知識のためです。.Max()を使用します。

最初の考えでは、.Max()は、最大を見つけるためにnumbersを1回通過するだけで、2番目の方法はすべてのものを並べ替えて最初のものを見つけなければなりません。したがって、それはO(n)対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 to Objectsについて話している場合は、いいえ、最適化しません。

おそらく、別の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（n）は - ソートに依存し、それはおそらく、O（nlog（n））があります。

私は明らかにコンパイラの中身を知っているわけではありませんが、あなたが求めているのは、並べ替えを実現して一つのアイテムだけを.maxと同じにする最適化です。

Answer 3

ためにLINQおよび/またはそうでないことを把握するのに十分な賢いコンパイラです列挙型全体をソートする必要があり、コードを.Max（）と本質的に同じにしますか？

号

見つけるための定量化方法はありますか？

ストップウォッチを持つ単純なベンチマーク：

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

はまた、[並べ替えは、（）でOutOfMemoryExceptionで失敗それを超えて、Max（）はそれを超えています。

Answer 4

OrderedEnumerableは、FirstとLast（）のリストをソートする必要がないことを知るのに十分なほどスマートに見えます。

注ライン223、TryGetFirst（） https://github.com/dotnet/corefx/blob/ed0ee133ac49cee86f10ca4692b1d72e337bc012/src/System.Linq/src/System/Linq/OrderedEnumerable.cs