LINQ查询性能与紧凑查询

Question

在检查LINQ的能力时,我编写了简单的QuickSort实现,
很高兴最终快速排序功能适合一行.
但是我注意到这个"一行"功能的性能与我原来的"直接"版本有很大不同.

这是在循环中调用快速排序函数10次的代码:

var r = new Random(DateTime.Now.Millisecond);
Stopwatch watch = new Stopwatch();
for (int i = 0; i < 10; i++)
{
    watch.Reset();
    var randomA = new int[100].Select(x => r.Next(100)).ToList();

    watch.Start();                
    var sorted = QuickSort<int>(randomA);
    watch.Stop();

    Console.WriteLine("Duration: {0} ms", watch.ElapsedMilliseconds);
}

Console.ReadLine();

两个QuickSort函数的实现与输出结果:

简单版本:

IEnumerable<T> QuickSort<T>(IEnumerable<T> a) where T : IComparable<T>
{
    if (a.Count() <= 1) return a;

    var pivot = a.First();
    IEnumerable<T> lesser = a.Skip(1).Where(x => x.CompareTo(pivot) < 0);
    IEnumerable<T> bigger = a.Skip(1).Where(x => x.CompareTo(pivot) >= 0);

    return QuickSort(lesser).Concat(new T[] { pivot }).Concat(QuickSort(bigger));
}

输出
持续时间:22 ms
持续时间:3 ms
持续时间:3 ms
持续时间:3 ms
持续时间:3 ms
持续时间:3 ms
持续时间:2 ms
持续时间:2 ms
持续时间:3 ms
持续时间:3 ms

一线实施:

IEnumerable<T> QuickSort<T>(IEnumerable<T> a) where T : IComparable<T>
{
    return a.Count() <= 1 ? a :                 
        QuickSort(a.Skip(1).Where(i => i.CompareTo(a.First()) < 0)).
        Concat(new T[] { a.First() }).                          
        Concat(QuickSort(a.Skip(1).Where(i => i.CompareTo(a.First()) >= 0)));  
}

输出
持续时间:24154 ms
持续时间:407 ms
持续时间:2281 ms
持续时间:2420 ms
持续时间:919 ms
持续时间:48777 ms
持续时间:4615 ms
持续时间:3115 ms
持续时间:1311 ms
持续时间:1631 ms

为什么性能会有这么大的差异？

Answer 1

原因是你a.First()每次都在重新计算- 如果你再次考虑这个:

public static IEnumerable<T> QuickSort<T>(IEnumerable<T> a) 
    where T : IComparable<T>
{
    if (a.Count() <= 1) return a;
    var pivot = a.First();
    return QuickSort(a.Skip(1).Where(i => i.CompareTo(pivot) < 0))
        .Concat(new T[] { pivot })
        .Concat(QuickSort(a.Skip(1).Where(i => i.CompareTo(pivot) >= 0)));
}

然后表现是一样的.

为了澄清一个实验 - 使用一个拦截器(一个平凡的,只是为了这个实验,不要在家里使用它,这是错误的)实现First()我们可以看到实际上First()被调用了多少次.

public static class TestHelper
{
    public static int firstCalledCounter = 0;
    public static TSource First<TSource>(this IEnumerable<TSource> source) 
    {
        firstCalledCounter++;
        Console.WriteLine("First called " + firstCalledCounter);
        IList<TSource> list = source as IList<TSource>;
        if (list != null)
        {
            if (list.Count > 0)
            {
                return list[0];
            }
            else return default(TSource);
        }
        else return default(TSource);
    }
}

这表明在"一个班轮"中a.First()被称为236376次,而在我们考虑a.First() 它的版本中它被称为98次.这解释了性能差异.