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

Question

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

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

Например:

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

На практике это означает, что 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 */ } 

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

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