manera más rápida para buscar una gran lista de textos grandes

Question

Tengo una aplicación de Windows escrita en C# que necesita cargar 250,000 filas desde la base de datos y proporciona una función de "buscar mientras escribe" lo que significa que el usuario escribe algo en un texto cuadro, la aplicación necesita buscar los 250,000 registros (que son, por cierto, una sola columna con 1000 caracteres en cada fila) usando like buscar y mostrar los registros encontrados.

El enfoque que siguió fue:

1- Las cargas de aplicación todos los registros en un escrito List<EmployeeData>

while (objSQLReader.Read()) 
{ 
    lstEmployees.Add(new EmployeesData(
     Convert.ToInt32(objSQLReader.GetString(0)), 
     objSQLReader.GetString(1), 
     objSQLReader.GetString(2))); 
} 

2- En caso TextChanged, Uso de LINQ, busco (con combinación de expresiones regulares) y conecte el IEnumerable<EmployeesData> a un ListView que está en modo virtual.

String strPattern = "(?=.*wood*)(?=.*james*)"; 
    IEnumerable<EmployeesData> lstFoundItems = from objEmployee in lstEmployees 
    where Regex.IsMatch(Employee.SearchStr, strPattern, RegexOptions.IgnoreCase) 
    select objEmployee; 
    lstFoundEmployees = lstFoundItems; 

3- El evento RetrieveVirtualItem se maneja para mostrar elementos en ListView para mostrar el elemento.

e.Item = new ListViewItem(new String[] { 
    lstFoundEmployees.ElementAt(e.ItemIndex).DateProjectTaskClient, 
    e.ItemIndex.ToString() }); 

Aunque el lstEmployees se carga relativamente rápido (1,5 segundos) para cargar la lista de SQL Server, buscar en TextChanged, se tarda más de 7 minutos para buscar usando LINQ. La búsqueda a través del servidor SQL directamente realizando una búsqueda LIKE lleva menos de 7 segundos.

¿Qué estoy haciendo mal aquí? ¿Cómo puedo hacer esta búsqueda más rápido (no más de 2 segundos)? Este es un requisito de mi cliente. Entonces, cualquier ayuda es muy apreciada. Por favor, ayuda ...

Answer 1

Ver mi respuesta al this question. Si necesita una respuesta instantánea (es decir, tan rápido como escribe un usuario), cargar los datos en la memoria puede ser una opción muy atractiva. Puede usar un poco de memoria, pero es muy rápido.

Aunque hay muchos caracteres (250K registros * 1000), ¿cuantos únicos hay disponibles valores? Una estructura en memoria basada en claves con punteros a registros que coincidan con esas claves realmente no tiene que ser tan grande, incluso teniendo en cuenta las permutaciones de esas claves.

Si los datos realmente no caben en la memoria o cambian con frecuencia, guárdelos en la base de datos y use la indexación de texto completo de SQL Server, que manejará búsquedas como esta mucho mejor que LIKE. Esto supone una conexión rápida desde la aplicación a la base de datos.

La indización de texto completa ofrece un potente conjunto de operadores/expresiones que se pueden utilizar para hacer que las búsquedas sean más inteligentes. Está disponible con la edición gratuita SQL Expression Edition, que manejará hasta 10 GB de datos.

Answer 2

Si los registros se pueden ordenar, es posible que desee ir con una búsqueda binaria, que es mucho, mucho más rápida para grandes conjuntos de datos. Hay varias implementaciones en colecciones .NET, como List<T> y Array.

Answer 3

Usted se deseando para precargar las cosas y elaborar una estructura de datos llamada trie

Es mucha memoria, pero es lo que recetó el doctor en este caso.

Answer 4

¿La columna de la base de datos que almacena los datos de texto tiene un índice? Si es así, algo similar al trie structure que Nicholas describió ya está en uso. Los índices en SQL Server se implementan usando B+ trees, que tienen un tiempo de búsqueda promedio en el orden de la base de registro 2 de n, donde n es la altura del árbol. Esto significa que si tiene 250,000 registros en la tabla, el número de operaciones requeridas para buscar es la base de registro 2 (250,000) o aproximadamente 18 operaciones.

Cuando carga toda la información en un lector de datos y luego utiliza una expresión LINQ, se trata de una operación lineal, (O) n, donde n es la longitud de la lista. En el peor de los casos, serán 250,000 operaciones. Si utiliza un DataView, habrá índices que se pueden usar para ayudar con la búsqueda, lo que mejorará drásticamente el rendimiento.

Al final del día si no hay demasiadas solicitudes presentadas contra el servidor de bases de datos, aproveche el optimizador de consultas para hacer esto. Siempre que la operación LIKE no se realice con un comodín en la parte frontal de la cadena (es decir, LIKE %some_string) (niega el uso de un índice) y hay un índice en la tabla, tendrá un rendimiento realmente rápido. Si hay demasiadas solicitudes que se enviarán al servidor de la base de datos, coloque toda la información en un DataView para que se pueda usar un índice, o utilice un diccionario como Tim sugirió anteriormente, que tiene un tiempo de búsqueda de O (1) (del orden de uno), suponiendo que el diccionario se implementa utilizando una tabla hash.