¿Cuál es la forma más rápida de buscar una lista <T> en varias propiedades?

Question

Tengo un proceso heredado que estoy convirtiendo a C# de otro idioma. Numerosos pasos en el ciclo de proceso a través de lo que puede ser una gran cantidad de registros (100K-200K) para hacer cálculos. Como parte de esos procesos, generalmente hace una búsqueda en otra lista para recuperar algunos valores. Normalmente movería este tipo de cosas a una declaración de SQL (y tenemos donde hemos podido), pero en estos casos no hay una manera fácil de hacerlo. En algunos lugares, intentamos convertir el código a un procedimiento almacenado y decidimos que no funcionaba tan bien como esperábamos.

Efectivamente, el código hace esto:

var match = cost.Where(r => r.ryp.StartsWith(record.form.TrimEnd()) && 
         r.year == record.year && 
         r.period == record.period).FirstOrDefault(); 

costo es un tipo de lista local. Si estuviera haciendo una búsqueda en un solo campo, probablemente solo movería esto a un diccionario. Los registros tampoco son siempre únicos.

Obviamente, esto es REALMENTE lento.

me encontré con la biblioteca de código abierto I4O que se puede construir índices, sin embargo, no para mí en varias consultas (y yo realmente no tienen el tiempo para intentar depurar el código fuente). Tampoco funciona con .StartsWith o .Contains (StartsWith es mucho más importante ya que muchas de las consultas originales aprovechan el hecho de que al buscar "A" encontraría una coincidencia en "ABC").

¿Hay algún otro proyecto (de código abierto o comercial) que haga este tipo de cosas?

EDIT:

lo hice un poco de búsqueda en base a la retroalimentación y encontró Power Collections que apoya a los diccionarios que tienen claves que no son únicos.

Probé ToLookup() que funcionó muy bien, todavía no es tan rápido como el código original, pero al menos es aceptable. Ha bajado de 45 segundos a 3-4 segundos. Echaré un vistazo a la estructura de Trie para las otras búsquedas.

Gracias.

Answer 1

Looping a través de una lista de elementos 100K-200K no lleva mucho tiempo. Encontrar objetos coincidentes dentro de la lista mediante el uso de bucles anidados (n^2) lleva mucho tiempo. Deduzco que esto es lo que estás haciendo (dado que tienes una asignación a una variable de coincidencia local).

Si desea unir rápidamente los elementos, use .ToLookup.

var lookup = cost.ToLookup(r => new {r.year, r.period, form = r.ryp}); 

foreach(var group in lookup) 
{ 
    // do something with items in group. 
} 

Sus criterios startsWith es problemático para la adaptación basada en claves. Una forma de abordar ese problema es ignorarlo al generar claves.

var lookup = cost.ToLookup(r => new {r.year, r.period }); 
var key = new {record.year, record.period}; 
string lookForThis = record.form.TrimEnd(); 
var match = lookup[key].FirstOrDefault(r => r.ryp.StartsWith(lookForThis)) 

Idealmente, crearía la búsqueda una vez y la reutilizaría para muchas consultas. Incluso si no lo hizo ... incluso si creó la búsqueda cada vez, aún será más rápido que n^2.

Answer 2

Sin duda puede hacer algo mejor que esto. Comencemos por considerar que los diccionarios no son útiles solo cuando se quiere consultar un campo; fácilmente puede tener un diccionario donde la clave es un valor inmutable que agrega muchos campos. Así, por esta consulta en particular, una mejora inmediata sería la creación de un tipo de clave:

// should be immutable, GetHashCode and Equals should be implemented, etc etc 
struct Key 
{ 
    public int year; 
    public int period; 
} 

y luego empaquetar sus datos en un IDictionary<Key, ICollection<T>> o similar donde T es el tipo de la lista actual. De esta forma, puede reducir mucho el número de filas consideradas en cada iteración.

El siguiente paso sería utilizar no un ICollection<T> como el tipo de valor, sino un trie (this parece prometedor), que es una estructura de datos adaptada a la búsqueda de cadenas que tienen un prefijo especificado.

Por último, una micro-optimización gratuita sería sacar el TrimEnd del circuito.

Ahora bien, todo esto solo se aplica al ejemplo específico dado y puede ser necesario volver a visitarlo debido a otras circunstancias específicas de su situación, pero en cualquier caso debería poder extraer ganancias prácticas de este o algo similar.