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 毫秒
持续时间：3 毫秒
持续时间：3 毫秒
持续时间：3 毫秒
持续时间：3 毫秒
持续时间：3 毫秒
持续时间：2 毫秒
持续时间：2 毫秒
持续时间：3 毫秒
持续时间：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 毫秒
持续时间：407 毫秒
持续时间：2281 毫秒
持续时间：2420 毫秒
持续时间：919 毫秒
持续时间：48777 毫秒
持续时间：4615 毫秒
持续时间：3115 毫秒
持续时间：1311 毫秒
持续时间：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()< 的版本中/code> 它被调用98次。这解释了性能差异。

Answer 2

一般来说，这两个示例的主要问题是（请注意，这并不能回答问题，因为更改此操作会对这两个示例产生影响）：

if (a.Count() <= 1) return a;

在这里，您只是检查是否有一个项目，但是，您正在调用 Count。如果 IEnumerable 实现确实实现了 ICollection，则每次都会枚举列表。

由于您递归地调用此函数，因此当 您不这样做时，您最终会迭代序列中的所有项目真的不必。

相反，您应该这样做：

if (!a.Skip(1).Any()) return a;

这样，您最多只迭代两个项目（跳过第一个，检查第二个是否存在）来确定序列中是否最多有一个项目。

请注意，对于较大的 N 值，您将遇到与 Count 相同的问题；这是这里的一个优化，因为N的值非常小。