Why is this Linq expression so much slower than the other?

Time of execution: foo(1) >>> foo(2) >> foo(3)

roughly: 1427349 >>> 14757 >> 1362

foo(3) is the most optimized algorithm among the three, so I'm not surprised it's the fastest. What's surprising to me is that foo(2) is so much faster than foo(1). My impression is that foo(2) sorts, while foo(1) is operating similarly to foo(3). May I know what is the cause the slowdown for foo(1)? Show me what's under the hood. Thanks!

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

Code testing was in linqpad, so you can ignore the .Dump() method.

Answers


The first is O(N²), because you iterate over the array once for each outer iteration. The second is O(N log N), because you are sorting first. The last is O(N), because you iterate over the array in a single pass with no loop inside each iteration.

Try this:

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

It should now be comparable with the third case, though not quite, since you have to traverse the array 1.5 times, on average (assuming only one element has the max value).


Need Your Help

Insert data in mysql by html form (and more..)

php html mysql forms row

First of all: I'm new into MYSQL/PHP :). I'm working on a simple script to learn php/mysql, but I'm stuck with several problems. I'm really sorry if some of these are already asked on this website,...

Absolute vs relative URLs

html url

I would like to know the differences between these two types of URLs: relative URLs (for pictures, CSS files, JS files, etc.) and absolute URLs.