Rendimiento LINQ en memoria

Question

Más que sobre LINQ para [inserte aquí su proveedor favorito], esta pregunta se trata de buscar o filtrar colecciones en memoria.

Sé que LINQ (o métodos de búsqueda/filtrado de extensión) funciona en objetos que implementan IEnumerable o IEnumerable<T>. La pregunta es: debido a la naturaleza de la enumeración, ¿es cada complejidad de consulta al menos O (n)?

Por ejemplo:

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

En este caso, cada algoritmo llevará al menos O (n) menos list se ordena con respecto a 'something', en cuyo caso la búsqueda debe tomar O (log (n)): debe ser una búsqueda binaria. Sin embargo, si entiendo correctamente, esta consulta se resolverá mediante enumeración, por lo que debería tomar O (n), incluso en list se solicitó anteriormente.

• ¿Hay algo que pueda hacer para resolver una consulta en O (log (n))?
• Si quiero rendimiento, ¿debería usar Array.Sort y Array.BinarySearch?

Answer 1

Incluso con la paralelización, sigue siendo O (n). El factor constante sería diferente (dependiendo de su número de núcleos) pero a medida que n variara, el tiempo total aún variaría linealmente.

Por supuesto, podría escribir sus propias implementaciones de los diversos operadores LINQ sobre sus propios tipos de datos, pero solo serían apropiadas en situaciones muy específicas; habría que asegurarse de que el predicado solo funcionaba los aspectos optimizados de los datos. Por ejemplo, si tiene una lista de personas ordenadas por edad, no lo ayudará con una consulta que trate de encontrar a alguien con un nombre particular :)

Para examinar el predicado, tendría usar árboles de expresión en lugar de delegados, y la vida se volvería mucho más difícil.

Sospecho que normalmente agregaría nuevos métodos que hacen obvio que está usando la naturaleza indexada/ordenada/lo que sea del tipo de datos, y que siempre funcionará correctamente. Por supuesto, no podría invocar fácilmente esos métodos adicionales desde expresiones de consulta, pero aún puede usar LINQ con notación de puntos.

Answer 2

Sí, tiene que ser así, porque la única forma de acceder a cualquier miembro de un IEnumerable es mediante el uso de sus métodos, lo que significa O (n).

Parece un caso clásico en el que los diseñadores de idiomas decidieron intercambiar el rendimiento por la generalidad.

Answer 3

Sí, el caso genérico es siempre O (n), como dijo Sklivvz.

Sin embargo, muchos métodos LINQ son un caso especial cuando el objeto que implementa IEnumerable realmente implementa, p. ICollection. (He visto esto para IEnumerable.Contiene al menos.)

En la práctica esto significa que LINQ IEnumerable.Contains llama al HashSet rápido. Contiene, por ejemplo, si el IEnumerable es realmente un HashSet.

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

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

Puede usar el reflector para verificar exactamente cómo se definen los métodos LINQ, así es como me di cuenta.

Ah, y también LINQ contiene los métodos IEnumerable.ToDictionary (asigna la clave al valor único) e IEnumerable.ToLookup (asigna la clave a varios valores). Esta tabla de diccionario/búsqueda se puede crear una vez y usar muchas veces, lo que puede acelerar algún código de LINQ intensivo por órdenes de magnitud.