Rendimiento LINQ en memoria

Question

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

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

Por ejemplo:

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

En este caso, cada algoritmo tomará al menos O (n) a menos que list esté ordenado con respecto a 'something', en cuyo caso la búsqueda debería tomar O (log (n)) : debería 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 <=> se ordenó previamente.

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

Answer 1

Incluso con paralelización, sigue siendo O (n). El factor constante sería diferente (dependiendo de su número de núcleos) pero como n variaba, el tiempo total seguiría variando linealmente.

Por supuesto, podría escribir sus propias implementaciones de los diversos operadores LINQ sobre sus propios tipos de datos, pero solo serían apropiados en situaciones muy específicas: tendría que saber con seguridad que el predicado solo operaba en el Aspectos optimizados de los datos. Por ejemplo, si tienes una lista de personas ordenada por edad, no te ayudará con una consulta que intente encontrar a alguien con un nombre en particular :)

Para examinar el predicado, tendría que 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á utilizando la naturaleza indexada / ordenada / cualquiera que sea el tipo de datos, y que siempre funcionará adecuadamente. No podría invocar fácilmente esos métodos adicionales a partir de expresiones de consulta, por supuesto, pero aún puede usar LINQ con notación de puntos.

Answer 2

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

Sin embargo, muchos métodos LINQ son casos especiales para 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 lo descubrí.

Ah, y también LINQ contiene los métodos IEnumerable.ToDictionary (asigna la clave a un solo valor) e IEnumerable.ToLookup (asigna la clave a varios valores). Esta tabla de búsqueda / diccionario se puede crear una vez y usar muchas veces, lo que puede acelerar algunos códigos intensivos en LINQ por orden de magnitud.

Answer 3

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

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