In-memory desempenho LINQ

Question

Mais do que sobre LINQ para [inserir o seu fornecedor favorito aqui], esta questão é de como pesquisar ou filtrar coleções em memória.

Eu sei (métodos ou pesquisar / extensão filtragem) LINQ funciona em objetos de aplicação IEnumerable ou IEnumerable<T>. A questão é:? por causa da natureza de enumeração, é toda a complexidade da consulta, pelo menos O (n)

Por exemplo:

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

Neste caso, cada algoritmo levará pelo menos O (n) , a menos list é ordenado com respeito a 'something', caso em que a pesquisa deve tomar O (log (n)) : deve ser uma busca binária. No entanto, se bem entendi, essa consulta será resolvido por meio de enumeração, por isso deve tomar O (n) , mesmo em list foi previamente ordenada.

• Existe algo que eu possa fazer para resolver uma consulta no O (log (n)) ?
• Se eu quiser performance, eu deveria usar Array.Sort e Array.BinarySearch?

Answer 1

Mesmo com paralelização, ainda é O (n). O factor constante seria diferente (dependendo do número de núcleos) mas como n variou o tempo total seria ainda variar linearmente.

Claro, você poderia escrever suas próprias implementações dos vários operadores LINQ sobre seus próprios tipos de dados, mas eles só seria apropriada em situações muito específicas - você tem que saber com certeza que o predicado única operado no aspectos optimizadas dos dados. Por exemplo, se você tem uma lista de pessoas que estão ordenados por idade, isso não vai ajudá-lo com uma consulta que tenta encontrar alguém com um nome especial:)

Para examinar o predicado, você teria que usar árvores em vez de delegados de expressão, ea vida se tornaria muito mais difícil.

Eu suspeito que eu normalmente adicionar novos métodos que tornam óbvio que você está usando o / indexada ordenou / whatever natureza do tipo de dados, e que irá trabalhar sempre de forma adequada. Você não poderia facilmente invocar esses métodos extras de expressões de consulta, é claro, mas você ainda pode usar LINQ com a notação de ponto.

Answer 2

Sim, o caso genérico é sempre O (n), como disse Sklivvz.

No entanto, muitos métodos LINQ caso especial para quando o objeto implementando IEnumerable realmente implementa por exemplo ICollection. (Eu vi isso por IEnumerable.Contains pelo menos.)

Na prática, isto significa que LINQ IEnumerable.Contains chama de HashSet.Contains rápidos, por exemplo, se o IEnumerable é realmente um HashSet.

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

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

Você pode usar reflector para verificar exatamente como os métodos LINQ são definidos, é assim que eu descobri isso.

Oh, e também LINQ contém métodos IEnumerable.ToDictionary (mapas chave para valor único) e IEnumerable.ToLookup (mapas chave para vários valores). Este dicionário / pesquisa de tabela pode ser criada uma vez e usado muitas vezes, o que pode acelerar algum código-LINQ intensivo por ordens de magnitude.

Answer 3

Sim, tem que ser, porque a única maneira de aceder a qualquer membro de uma IEnumerable é usando seus métodos, o que significa que o (n).

Parece um caso clássico em que os projetistas da linguagem decidiu desempenho do comércio para a generalidade.