Является ли linq более эффективным, чем кажется на поверхности?

13

Если я напишу что-то вроде этого:

var things = mythings
    .Where(x => x.IsSomeValue)
    .Where(y => y.IsSomeOtherValue)

Это так же, как:

var results1 = new List<Thing>();
foreach(var t in mythings)
    if(t.IsSomeValue)
        results1.Add(t);

var results2 = new List<Thing>();
foreach(var t in results1)
    if(t.IsSomeOtherValue)
        results2.Add(t);

Или под покровами есть какая-то магия, которая работает примерно так:

var results = new List<Thing>();
foreach(var t in mythings)
    if(t.IsSomeValue && t.IsSomeOtherValue)
        results.Add(t);

Или это что-то совершенно другое?

ConditionRacer
источник
4
Вы можете просмотреть это в ILSpy.
ChaosPandion
1
Это скорее второй пример, чем первый, но второй ответ ChaosPandion о том, что ILSpy - ваш друг.
Майкл

Ответы:

27

LINQ-запросы ленивы . Это означает, что код:

var things = mythings
    .Where(x => x.IsSomeValue)
    .Where(y => y.IsSomeOtherValue);

очень мало Исходный enumerable ( mythings) перечисляется только тогда, когда полученный enumerable ( things) используется, например, foreachциклом .ToList()или .ToArray().

Если вы звоните things.ToList(), это примерно эквивалентно вашему последнему коду, возможно, с некоторыми (обычно незначительными) издержками от перечислителей.

Аналогично, если вы используете цикл foreach:

foreach (var t in things)
    DoSomething(t);

По производительности он похож на:

foreach (var t in mythings)
    if (t.IsSomeValue && t.IsSomeOtherValue)
        DoSomething(t);

Некоторые из преимуществ производительности при использовании метода лени для перечислимых данных (в отличие от вычисления всех результатов и сохранения их в списке) заключаются в том, что он использует очень мало памяти (поскольку за один раз сохраняется только один результат) и что значительного стоимость.

Если перечислимое перечислено только частично, это особенно важно. Рассмотрим этот код:

things.First();

Способ реализации LINQ mythingsбудет перечисляться только до первого элемента, который соответствует вашим условиям. Если этот элемент находится в начале списка, это может значительно повысить производительность (например, O (1) вместо O (n)).

Cyanfish
источник
1
Одно из различий в производительности между LINQ и использованием эквивалентного кода foreachзаключается в том, что LINQ использует вызовы делегатов, которые имеют некоторые накладные расходы. Это может быть важно, когда условия выполняются очень быстро (что они часто делают).
svick
2
Вот что я имел в виду под заголовком перечислителя. Это может быть проблемой в некоторых (редких) случаях, но, по моему опыту, это не очень часто - обычно время, которое требуется для этого, очень мало, или оно значительно перевешивает другие операции, которые вы выполняете.
Cyanfish
Противное ограничение ленивой оценки Линка состоит в том, что нет способа сделать «снимок» перечисления, кроме как с помощью методов, подобных ToListили ToArray. Если бы такая вещь была должным образом встроена IEnumerable, можно было бы попросить список, чтобы «сделать снимок» любых аспектов, которые могут измениться в будущем, без необходимости создавать все.
суперкат
7

Следующий код:

var things = mythings
    .Where(x => x.IsSomeValue)
    .Where(y => y.IsSomeOtherValue);

Ничто не эквивалентно, из-за ленивой оценки ничего не произойдет.

var things = mythings
    .Where(x => x.IsSomeValue)
    .Where(y => y.IsSomeOtherValue)
    .ToList();

Отличается, потому что оценка будет запущена.

Каждый предмет mythingsбудет отдан первому Where. Если оно пройдет, оно будет передано второму Where. Если он пройдет, он будет частью вывода.

Так что это выглядит примерно так:

var results = new List<Thing>();
foreach(var t in mythings)
{
    if(t.IsSomeValue)
    {
        if(t.IsSomeOtherValue)
        {
            results.Add(t);
        }
    }
}
Кирилл Гандон
источник
7

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

Давайте просто представьте , что вы звоните ToListна things.

Реализация Enumerable.Whereвозвращает а Enumerable.WhereListIterator. Когда вы вызываете Whereэто WhereListIterator(также называемое цепочкой Where-calls), вы больше не звоните Enumerable.Where, но Enumerable.WhereListIterator.Where, который фактически объединяет предикаты (используя Enumerable.CombinePredicates).

Так что это больше похоже if(t.IsSomeValue && t.IsSomeOtherValue).

леность
источник
«возвращает Enumerable.WhereListIterator» заставил его щелкнуть для меня. Вероятно, очень простая концепция, но это то, что я пропустил с ILSpy. Спасибо
ConditionRacer
Посмотрите повторное внедрение этой оптимизации Джоном Скитом, если вы заинтересованы в более глубоком анализе.
Servy
1

Нет, это не то же самое. В вашем примере things- это объект IEnumerable, который на данный момент является всего лишь итератором, а не фактическим массивом или списком. Более того, поскольку thingsон не используется, цикл даже не оценивается. Тип IEnumerableпозволяет перебирать элементы yield-ed с помощью инструкций Linq и обрабатывать их далее с помощью большего количества инструкций, что означает, что в итоге у вас действительно будет только один цикл.

Но как только вы добавляете инструкцию типа .ToArray()или .ToList(), вы заказываете создание фактической структуры данных, тем самым ограничивая вашу цепочку.

См. Этот связанный вопрос SO: /programming/2789389/how-do-i-implement-ienumerable

Жюльен Геро
источник