为什么这个Linq表达式比另一个慢得多？

Question

执行时间:foo(1)>>> foo(2)>> foo(3)

大致:1427349 >>> 14757 >> 1362

foo(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;
    }
}

代码测试在linqpad中,因此您可以忽略该.Dump()方法.

Answer 1

第一个是O(N²),因为你为每个外部迭代迭代一次数组.第二个是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倍(假设只有一个元素具有最大值).