Производительность запросов 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 мс

Реализация в одну строку:

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 мс

Почему такая большая разница в производительности?

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 раз.Это объясняет разницу в производительности.

Answer 2

Основным нарушителем в целом для обоих примеров является следующее (обратите внимание, что это не отвечает на вопрос, поскольку изменение этой операции повлияет на оба примера):

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

Здесь вы просто проверяетечтобы узнать, есть ли у вас один предмет, и все же вы звоните Count.В случае, если реализация IEnumerable<T> реализует ICollection<T>, она будет перечислять список каждый раз.

Так как вы вызываете это рекурсивно, вы заканчиваете итерацией по всем элементам в последовательности, когда вам на самом деле не нужно .

Скорее, вы должны сделать это:

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

Таким образом, вы перебираете не более двух элементов (пропускаяво-первых, проверяя наличие второго), чтобы определить, есть ли у вас не более одного элемента в последовательности.

Обратите внимание, что при больших значениях N вы столкнетесь с теми же проблемами, что и выс Count;это оптимизация, потому что значение N очень мало.