LINQ to Objects y performance mejorada con un índice?

Question

Estoy usando LINQ to Objects y me pregunto si es posible mejorar el rendimiento de mis consultas haciendo uso de un índice que tengo. Esto se explica mejor con un ejemplo. Imagine un tipo simple ...

public class Person 
{ 
    public int Age; 
    public string FirstName; 
    public string LastName; 
} 

Y una simple consulta que haría en contra de ella ...

List<Person> people = new List<Person>(); 

// 'people' populated with 50,000 instances... 

var x = from t in people 
     where t.Age > 18 && t.Age < 21 
     select t; 

Si entiendo LINQ a objetos correctamente, entonces la ejecución del método de extensión Cuando enumerará todas las 50,000 instancias en la colección de personas para encontrar las 100 que realmente coinciden. Da la casualidad que ya tengo un índice de la colección de personas ordenada por edad. Así ...

SortedList<int, Person> ageSorted = new SortedList<int, Person>(); 

Es evidente que tendría sentido si podía conseguir la Dónde utilizar SortedList de modo que ya no tiene que enumerar todos los 50.000 casos, en lugar de encontrar el rango de 100 entradas coincidentes y así ahorrar hora.

¿Es posible extender LINQ a Objetos para habilitar mi situación? ¿Ya es posible, pero me falta la técnica?

Answer 1

Ya hay un proyecto que creo que hace exactamente eso - i4o. No puedo decir que lo haya usado yo mismo, pero parece que es el tipo de cosa que quieres ... es posible que tengas que hacer malabares con tu código existente un poco, pero ciertamente vale la pena mirarlo.

Si ese no hace ayuda, al menos podría escribir sus propios métodos de extensión en SortedList<TKey, TValue>. Probablemente no pueda fácilmente usar su cláusula actual where, pero podría usar sus propios métodos tomando un valor mínimo y máximo. Es posible que también desee que se apliquen a IList<T> donde afirme que ya ha ordenado los valores de forma adecuada (según algunos comparadores).

Por ejemplo (no está comprobado):

public static IEnumerable<T> Between<T, TKey>(this IList<T> source, 
               Func<T, TKey> projection, 
               TKey minKeyInclusive, 
               TKey maxKeyExclusive, 
               IComparer<TKey> comparer) 
{ 
    comparer = comparer ?? Comparer<TKey>.Default; 

    // TODO: Find the index of the lower bound via a binary search :) 
    // (It's too late for me to jot it down tonight :) 
    int index = ...; // Find minimum index 

    while (index < source.Count && 
      comparer.Compare(projection(source[index]), maxKeyExclusive) < 0) 
    { 
     yield return source[index]; 
     index++; 
    } 
} 

(Si sólo tiene List<T> en lugar de IList<T>, podría utilizar List<T>.BinarySearch, a pesar de que había necesidad de construir una costumbre IComparer<T>.)

también , eche un vistazo a SortedSet<T> en .NET 4.

Answer 2

La sintaxis de la consulta LINQ en realidad utiliza cualquier método de extensión llamado Where que coincida con la firma, por lo que puede alwa Y escribe el tuyo que maneje tu tipo específico de la forma que quieras.

public static IEnumerable<Person> Where(this IEnumerable<Person> collection, Func<Person, bool> condition) 
    { 
     Console.WriteLine("My Custom 'Where' method called"); 
     return System.Linq.Enumerable.Where(collection, condition); 
    } 

...

 var x = from t in people 
       where t.Age > 18 && t.Age < 21 
       select t; //Will print "My Custom 'Where' method called" 

continuación, puede aplicar cualquier lógica que desea. Creo que las reglas de sobrecarga de métodos normales se aplican para determinar qué método de extensión Where se llamaría.

Answer 3

Tiene razón en que la consulta que escribió enumerará toda la lista, ya que obviamente LINQ no puede asumir nada sobre sus datos.

Si usted tiene un SortedList, puede explotar que el uso de los métodos de LINQ SkipWhile/takeWhile:

var x = x.SkipWhile(kv => kv.Key <= 18).TakeWhile(kv => kv.Key < 21) 

EDITAR

@ Davy8 es correcto, por supuesto, que la peor de los casos esto todavía tiene el mismo rendimiento. Vea las otras respuestas para encontrar el primer valor de manera más rápida.

Si usted tiene que hacer esta operación más de una vez para diferentes rangos de edad entonces es probable que también se puede acelerar mediante la agrupación de la edad:

var byAge = people.GroupBy(p => p.Age); 

var x = from grp in byAge 
     where grp.Key > 18 && grp.Key < 21 
     from person in grp 
     select person; 

Answer 4

En un recipiente preclasificados, la eficiencia se logra encontrando el primer elemento rápidamente Una vez que encuentre el primer elemento, simplemente obtenga linealmente los siguientes elementos hasta que encuentre el final de su rango.

Asumiendo que su SortedList está ordenada por Person.Age, se encuentra el primer elemento de la gama usando SortedList.IndexOfKey, que es un algoritmo binary search; por lo tanto, este método es una operación O (log n).

(No creo que usted puede cambiar su código para la Enumerable.Where de repente se vuelve más inteligente y encuentra el área de alcance mediante el uso de búsqueda binaria.)

--- --- EDITAR

En realidad, lo que realmente necesita es List.BinarySearch o Array.BinarySearch. El SortedList.IndexOfKey no le permitirá obtener el índice de la coincidencia más cercana en caso de que no exista coincidencia exacta. O simplemente puede implementar la búsqueda binaria usted mismo.