Есть ли случаи, когда LINQ .Where () будет быстрее, чем O (N)?

Question

Думаю, название хорошо описывает мои мысли:)

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

Извините, если этот вопрос немного расплывчатый, я просто хочу подтвердить мои мысли о том, что вы должны быть "осторожны" при использовании LINQ.

[РЕДАКТИРОВАТЬ] Просто чтобы уточнить - я думаю с точки зрения Linq to Objects здесь:)

Answer 1

Это зависит от того, как вы его используете и с чем сравниваете.

Я видел много реализаций, использующих foreache s, которые были бы намного быстрее с linq. Например. потому что они забывают сломать или потому что они возвращают слишком много предметов. Хитрость заключается в том, что лямбда-выражения выполняются, когда элемент фактически используется. Когда в конце вы наберете First, это может закончиться всего одним вызовом.

Таким образом, когда вы соединяете в цепочку Where s, если элемент не проходит первое условие, он также не будет проверен на второе условие. это похоже на оператор &&, который не оценивает условие на правой стороне, если первое не выполнено.

Можно сказать, что это всегда O (N). Но N - это не количество элементов в источнике, а минимальное количество элементов, необходимое для создания целевого набора. Это очень хорошая оптимизация, ИМХО.

Answer 2

Зависит от провайдера.Для Linq to Objects это будет O (n), но для Linq to SQL или Entities он может в конечном итоге использовать индексы, чтобы победить это.Для объектов, если вам нужна функциональность Where, вам, вероятно, все равно понадобится O (n).Linq будет почти наверняка иметь большую константу, в основном из-за вызовов функций.

Answer 3

Вот проект, который обещает ввести индексирование для объектов LINQ2Object. Это должно обеспечить лучшее асимптотическое поведение: http://i4o.codeplex.com/