なぜこのLinq式は他のものよりもずっと遅いですか？実行の

Question

時間：FOO（1）>>> FOO（2）>> FOO（3）

略：1427349 >>> 14757 >> 1362

fooは（3）最も最適化アルゴリズムであります3人のうち、私はそれが最も速いのは驚きではありません。 私には驚きましたが、foo（2）はfoo（1）よりもはるかに高速です。私の印象はfoo（2）のソートですが、foo（1）はfoo（3）と同様に動作しています。 foo（1）の減速の原因は何か分かりますか？フードの下にあるものを私に見せてください。ありがとう！

void Main() 
{ 
    Random r = new Random(); 
    for(int i = 0; i < array.Length; i++) 
    { 
     array[i] = new A(r.Next(int.MaxValue)); 
    } 

    foo(1); 
    foo(2); 
    foo(3); 
} 

A[] array = new A[10000]; 
static Stopwatch sw = new Stopwatch(); 

public void foo(int s) 
{ 
    sw.Reset(); 
    sw.Start(); 

    switch(s) 
    { 
     case 1: 
      array.First(x => (x.value == array.Max(y => y.value))).Dump(); 
      break; 
     case 2: 
      array.OrderBy(x => x.value) 
      .Last() 
      .Dump();  
      break; 
     case 3: 
      {   
       int max = array[0].value; 
       int index = 0; 
       int i = 0; 
       for(; i < array.Length; i++) 
       { 
        if(array[i].value >= max) 
        { 
         max = array[i].value; 
         index = i; 
        } 
       } 
       array[index].Dump(); 
      } 
      break; 
    } 

    sw.Stop(); 
    sw.Dump(); 
} 
class A 
{ 
    public int value; 
    public A(int value) 
    { 
     this.value = value; 
    } 
} 

コードのテストあなたが.Dump()法を無視することができますので、linqpadにありました。

Answer 1

最初のものはO（N ²）です。外側の反復ごとに1回ずつ配列を反復処理するためです。 2番目はO（N log N）です。なぜなら、最初にソートしているからです。最後のものはO（N）です。なぜなら、各反復の中にループのない単一パスで配列を反復処理するからです。

ことは、これを試してみてください：

 case 1: 
      var max = array.Max(x => x.value); 
      array.First(x => x.value == max).Dump(); 
      break; 

あなたは、平均して、配列に1.5倍を通過する必要があるためではない、非常に、（一つだけの要素が最大値を持っていると仮定して）にもかかわらずそれは今、第三の場合と同等でなければなりません。