Отложенное выполнение List‹T› с использованием Linq

Предположим, у меня есть List<T> с 1000 элементами.

Затем я передаю это методу, который фильтрует этот список. По мере прохождения различных случаев (например, их может быть 50) над List<T> может выполняться до 50 различных операций Linq Where().

Я заинтересован в том, чтобы эта работа прошла как можно быстрее. Поэтому я не хочу, чтобы это List<T> фильтровалось каждый раз, когда над ним выполняется Where().

По сути, мне нужно отложить фактическое манипулирование List<T> до тех пор, пока не будут применены все фильтры.

Это делается изначально компилятором? Или только когда я вызываю .ToList() для IEnumerable, который возвращает List<T>.Where(), или я должен выполнять операции Where() над X (где X = List.AsQueryable())?

Надеюсь, это имеет смысл.


list generics linq deferred-execution
person maxp    schedule 17.06.2010    source источник

Ответы (3)


arrow_upward
4
arrow_downward

Да, отложенное выполнение поддерживается изначально. Каждый раз, когда вы применяете запрос или лямбда-выражение к своему списку, запрос сохраняет все выражения, которые выполняются только тогда, когда вы вызываете .ToList() в запросе.

person this. __curious_geek    schedule 17.06.2010
comment
Знаете ли вы, какое снижение скорости возникает при вызове List‹T›.AsQueryable().ToList() (т. е. списка без вызываемых выражений)? - person maxp; 17.06.2010
comment
Редактировать: 32767 x List‹T›.AsQueryable().ToList() заняло 120 мс, поэтому в основном незначительно. - person maxp; 17.06.2010

arrow_upward
3
arrow_downward

Каждый вызов Where будет создавать новый объект, который знает о вашем фильтре и вызываемой последовательности.

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

Итак, если вы вызываете Where 50 раз (как в list.Where(...).Where(...).Where(...), вы получаете что-то, что должно проходить вверх и вниз по стеку вызовов не менее 50 раз для каждого возвращаемого элемента. Насколько это повлияет на производительность? Я не знаю: Вы должны измерить это.

Одна из возможных альтернатив — построить дерево выражений, а затем скомпилировать его в делегат в конце и затем вызвать Where. Это, безусловно, требует немного больше усилий, но может оказаться более эффективным. По сути, это позволит вам изменить это:

list.Where(x => x.SomeValue == 1)
    .Where(x => x.SomethingElse != null)
    .Where(x => x.FinalCondition)
    .ToList()

в

list.Where(x => x.SomeValue == 1 && x.SomethingElse != null && x.FinalCondition)
    .ToList()

Если вы знаете, что собираетесь просто комбинировать множество фильтров "где", это может оказаться более эффективным, чем использование IQueryable<T>. Как всегда, проверьте производительность самого простого решения, прежде чем делать что-то более сложное.

person Jon Skeet    schedule 17.06.2010
comment
В предыдущем коде эта проблема решалась с помощью динамической библиотеки Linq (weblogs.asp.net/scottgu/archive/2008/01/07/), который только что построил длинную строку «где». Идея хороша, но без учета времени, я все же уверен, что это медленнее, чем просто дробить, где вместе, поскольку он должен анализировать строку bleh. - person maxp; 17.06.2010
comment
@maxp: делать это динамически, вероятно, будет медленнее, да, но вам не обязательно делать это динамически. Для безопасного выполнения всего этого можно использовать деревья выражений и встроить их в собственный IL с помощью LambdaExpression.Compile. - person Jon Skeet; 17.06.2010
comment
Я хотел прокомментировать ваш ответ, рассказав об оптимизации производительности для массивов и List‹T› внутри методов расширения Enumerable.Where. Однако я заметил, что эти оптимизации никак не влияют на правильность вашего ответа. Хотя эти оптимизации предотвращают перенос 50 итераторов, они не предотвратят перенос 50 делегатов и, следовательно, не предотвратят глубокий стек вызовов на 50 вызовов. Лучше всего для производительности действительно будет один единственный делегат. - person Steven; 17.06.2010

arrow_upward
0
arrow_downward

В вопросе и комментариях так много неудач. Ответы хороши, но не бьют достаточно сильно, чтобы преодолеть неудачу.

Предположим, у вас есть список и запрос.

List<T> source = new List<T>(){  /*10 items*/ };
IEnumerable<T> query = source.Where(filter1);
query = query.Where(filter2);
query = query.Where(filter3);
...
query = query.Where(filter10);

Выполняется ли [ленивая оценка] компилятором изначально?

Нет. Ленивая оценка связана с реализацией Enumerable.Where.

Этот метод реализован с использованием отложенного выполнения. Немедленное возвращаемое значение — это объект, в котором хранится вся информация, необходимая для выполнения действия. Запрос, представленный этим методом, не выполняется до тех пор, пока объект не будет пронумерован либо путем прямого вызова его метода GetEnumerator, либо с помощью foreach в Visual C# или For Each в Visual Basic.

штраф за скорость при вызове List.AsQueryable().ToList()

Не звоните AsQueryable, вам нужно использовать только Enumerable.Where.

таким образом, не предотвратит глубокий стек вызовов на 50 вызовов

Глубина стека вызовов гораздо менее важна, чем высокоэффективный фильтр. Если вы сможете уменьшить количество элементов раньше, вы уменьшите количество вызовов метода позже.

person Amy B    schedule 17.06.2010
comment
Для протокола: неудача = непонимание и не поиск используемых методов. - person Amy B; 17.06.2010