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

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

8 голосов
/ 27 сентября 2008

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

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

Например: 

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

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

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

Ответы [ 3 ]

5 голосов
/ 27 сентября 2008

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

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

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

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

3 голосов
/ 27 сентября 2008

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

Тем не менее, многие методы LINQ имеют особый случай, когда объект, реализующий IEnumerable, фактически реализует, например, ICollection. (Я видел это для 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 */ }

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

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

2 голосов
/ 27 сентября 2008

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

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

...