Производительность LINQ в памяти

Question

Больше, чем о LINQ для [вставьте здесь вашего любимого провайдера], этот вопрос касается поиска или фильтрации коллекций в памяти.

Я знаю, что LINQ (или методы расширения поиска / фильтрации) работает в объектах, реализующих IEnumerable или IEnumerable<T>.Вопрос в том,: из-за природы перечисления, является ли каждый запрос сложным по крайней мере O (n)?

Например:

var result = list.FirstOrDefault(o => o.something > n);

В этом случае каждый алгоритм займет не менее O (n) если не list упорядочен в отношении 'something', в этом случае поиск должен занять O(логарифм(n)):это должен быть двоичный поиск.Однако, если я правильно понимаю, этот запрос будет разрешен с помощью перечисления, поэтому он должен занять O (n), даже в list был ранее заказан.

• Есть ли что-то, что я могу сделать для решения запроса в O(логарифм(n))?
• Если мне нужна производительность, должен ли я использовать Array.Сортировка и Array.BinarySearch?

Answer 1

Даже при распараллеливании это все равно O(n).Постоянный коэффициент был бы другим (в зависимости от вашего количества ядер), но при изменении n общее время все равно менялось бы линейно.

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

Чтобы исследовать предикат, вам пришлось бы использовать деревья выражений вместо делегатов, и жизнь стала бы намного сложнее.

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

Answer 2

Да, общий случай всегда равен O (n), как сказал Sklivvz.

Однако многие методы LINQ являются особым случаем, когда объект, реализующий IEnumerable, фактически реализует, напримерМоя коллекция.(Я видел это для IEnumerable.Содержит как минимум.)

На практике это означает, что LINQ IEnumerable.Contains вызывает быстрый HashSet.Contains, например, если IEnumerable на самом деле является HashSet.

IEnumerable<int> mySet = new HashSet<int>();

// calls the fast HashSet.Contains because HashSet implements ICollection.
if (mySet.Contains(10)) { /* code */ }

Вы можете использовать reflector, чтобы точно проверить, как определены методы LINQ, вот как я это понял.

О, а также LINQ содержит методы IEnumerable.ToDictionary (сопоставляет ключ с одним значением) и IEnumerable.ToLookup (сопоставляет ключ с несколькими значениями).Эта таблица словаря / подстановки может быть создана один раз и использоваться много раз, что может ускорить некоторый код с интенсивным использованием LINQ на порядки.

Answer 3

Да, так и должно быть, потому что единственный способ доступа к любому члену IEnumerable заключается в использовании его методов, что означает O (n).

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