Имеет ли значение порядок функций LINQ?

114

В принципе, как гласит вопрос ... имеет ли значение порядок функций LINQ с точки зрения производительности ? Очевидно, результаты все равно должны быть идентичными ...

Пример:

myCollection.OrderBy(item => item.CreatedDate).Where(item => item.Code > 3);
myCollection.Where(item => item.Code > 3).OrderBy(item => item.CreatedDate);

Оба возвращают мне одинаковые результаты, но находятся в другом порядке LINQ. Я понимаю, что изменение порядка некоторых элементов приведет к другим результатам, и меня это не волнует. Моя главная забота заключается в том, чтобы знать, может ли порядок повлиять на производительность при получении тех же результатов. И не только для двух вызовов LINQ, которые я сделал (OrderBy, Where), но и для любых вызовов LINQ.

Майкл
источник
9
Классный вопрос.
Роберт С.
Тем более очевидно, что оптимизация провайдера имеет значение в более педантичном случае вроде var query = myCollection.OrderBy(item => item.Code).Where(item => item.Code == 3);.
Марк Херд
1
Вы заслуживаете одобрения :), интересные вопросы. Я учту это, когда напишу свой Linq to Entities в EF.
GibboK
1
@GibboK: будьте осторожны при попытке «оптимизировать» запросы LINQ (см. Ответ ниже). Иногда вы ничего не оптимизируете. При оптимизации лучше всего использовать профилировщик.
myermian

Ответы:

147

Это будет зависеть от используемого поставщика LINQ. Для LINQ to Objects это, безусловно, может иметь огромное значение. Допустим, у нас действительно есть:

var query = myCollection.OrderBy(item => item.CreatedDate)
                        .Where(item => item.Code > 3);

var result = query.Last();

Это требует , чтобы вся коллекция будет отсортирован и затем фильтруют. Если бы у нас был миллион элементов, только один из которых имел код больше 3, мы бы потратили много времени на упорядочивание результатов, которые были бы выброшены.

Сравните это с обратной операцией, сначала фильтруя:

var query = myCollection.Where(item => item.Code > 3)
                        .OrderBy(item => item.CreatedDate);

var result = query.Last();

На этот раз мы упорядочиваем только отфильтрованные результаты, что в случае примера «только один элемент, соответствующий фильтру» будет намного более эффективным - как во времени, так и в пространстве.

Это также может иметь значение, правильно ли выполняется запрос или нет. Рассматривать:

var query = myCollection.Where(item => item.Code != 0)
                        .OrderBy(item => 10 / item.Code);

var result = query.Last();

Это нормально - мы знаем, что никогда не будем делить на 0. Но если мы выполним упорядочение до фильтрации, запрос вызовет исключение.

Джон Скит
источник
2
@Jon Skeet, есть ли документация о Big-O для каждого из поставщиков и функций LINQ? Или это просто случай, когда «каждое выражение уникально для данной ситуации».
Майкл
1
@michael: Это не очень четко задокументировано, но если вы читаете мою серию блогов "Edulinq", я думаю, что говорю об этом достаточно подробно.
Джон Скит
3
@michael: вы можете найти это здесь msmvps.com/blogs/jon_skeet/archive/tags/Edulinq/default.aspx
VoodooChild
3
@gdoron: Честно говоря, не совсем понятно, что вы имеете в виду. Похоже, вы захотите написать новый вопрос. Имейте в виду, что Queryable вообще не пытается интерпретировать ваш запрос - его задача состоит исключительно в том, чтобы сохранить ваш запрос, чтобы что-то еще могло его интерпретировать. Также обратите внимание, что LINQ to Objects даже не использует деревья выражений.
Джон Скит
1
@gdoron: Дело в том, что это работа провайдера, а не работа Queryable. И это не должно иметь значения при использовании Entity Framework. Однако это важно для LINQ to Objects. Но да, непременно задайте другой вопрос.
Джон Скит
17

Да.

Но в чем именно заключается разница в производительности, зависит от того, как провайдер LINQ оценивает базовое дерево выражений.

Например, ваш запрос может выполняться быстрее во второй раз (с предложением WHERE первым) для LINQ-to-XML, но быстрее в первый раз для LINQ-to-SQL.

Чтобы точно определить разницу в производительности, вы, скорее всего, захотите профилировать свое приложение. Однако, как всегда с такими вещами, преждевременная оптимизация обычно не стоит усилий - вы вполне можете обнаружить, что другие проблемы, помимо производительности LINQ, более важны.

Джереми МакГи
источник
5

В вашем конкретном примере это может повлиять на производительность.

Первый запрос: ваш OrderByвызов должен пройти через всю исходную последовательность, включая те элементы, у которых Code3 или меньше. Предложение Whereзатем также должно перебрать всю упорядоченную последовательность.

Второй запрос: WhereВызов ограничивает последовательность только теми элементами, у которых Codeбольше 3. В этом случае OrderByвызову необходимо пройти только по сокращенной последовательности, возвращаемой Whereвызовом.

LukeH
источник
3

В Linq-To-Objects:

Сортировка довольно медленная и использует O(n)память. Whereс другой стороны, относительно быстро и использует постоянную память. Так что делать Whereсначала будет быстрее, а для больших коллекций - значительно быстрее.

Уменьшение нагрузки на память также может быть значительным, поскольку, по моему опыту, выделения в куче больших объектов (вместе с их коллекцией) относительно дороги.

CodesInChaos
источник
1

Очевидно, результаты все равно должны быть идентичными ...

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

myCollection.OrderBy(o => o).Distinct();
myCollection.Distinct().OrderBy(o => o);
BlueRaja - Дэнни Пфлугхофт
источник
1
Нет, я имел в виду, что результаты должны быть идентичными, даже если рассматривать оптимизацию. Нет смысла что-то «оптимизировать» и получать другой результат.
Майкл
1

Стоит отметить, что вы должны быть осторожны при рассмотрении того, как оптимизировать запрос LINQ. Например, если вы используете декларативную версию LINQ для выполнения следующих действий:

public class Record
{
    public string Name { get; set; }
    public double Score1 { get; set; }
    public double Score2 { get; set; }
}


var query = from record in Records
            order by ((record.Score1 + record.Score2) / 2) descending
            select new
                   {
                       Name = record.Name,
                       Average = ((record.Score1 + record.Score2) / 2)
                   };

Если по какой-либо причине вы решили «оптимизировать» запрос, сначала сохранив среднее значение в переменной, вы не получите желаемых результатов:

// The following two queries actually takes up more space and are slower
var query = from record in Records
            let average = ((record.Score1 + record.Score2) / 2)
            order by average descending
            select new
                   {
                       Name = record.Name,
                       Average = average
                   };

var query = from record in Records
            let average = ((record.Score1 + record.Score2) / 2)
            select new
                   {
                       Name = record.Name,
                       Average = average
                   }
            order by average descending;

Я знаю, что не многие люди используют декларативный LINQ для объектов, но это хорошая пища для размышлений.

myermian
источник
0

Это зависит от актуальности. Предположим, что у вас очень мало элементов с кодом Code = 3, тогда следующий заказ будет работать с небольшим набором коллекции, чтобы получить заказ по дате.

Если у вас много элементов с одинаковой CreatedDate, то следующий порядок будет работать с большим набором коллекции, чтобы получить порядок по дате.

Итак, в обоих случаях будет разница в производительности.

Панкадж Упадхьяй
источник