¿Cuál es la manera más rápida de filtrar una lista de cadenas al hacer una lista de Intellisense/Autocomplete?

Question

Estoy escribiendo un Intellisense/Autocomplete como el que encuentras en Visual Studio. Todo está bien hasta cuando la lista contiene probablemente más de 2000 elementos.

estoy usando una declaración de LINQ simple para hacer el filtrado:

var filterCollection = from s in listCollection 
         where s.FilterValue.IndexOf(currentWord,  
         StringComparison.OrdinalIgnoreCase) >= 0 
         orderby s.FilterValue 
         select s; 

entonces asignar esta colección para ItemSource de un cuadro de lista de WPF, y ese es el final de la misma, funciona bien.

Teniendo eso en cuenta, el Listbox también se virtualiza también, por lo que solo habrá como máximo de 7 a 8 elementos visuales en la memoria y en el árbol visual.

Sin embargo, la advertencia ahora es que, cuando el usuario escribe extremadamente rápido en el richtextbox, y en cada tecla ejecuto el filtrado + enlace, existe esta condición de semirreproducción, o filtrado fuera de sincronización, como el primero El filtrado de los trazos clave todavía podría estar haciendo su trabajo de filtrado o enlace, mientras que el cuarto trazo clave también está haciendo lo mismo.

Sé que podría demorarme un poco antes de aplicar el filtro, pero estoy tratando de lograr un filtrado perfecto como el de Visual Studio.

No estoy seguro de dónde se encuentra exactamente mi problema, así que también lo estoy atribuyendo al funcionamiento de cadena de IndexOf, o tal vez mi lista de cadenas podría optimizarse en algún tipo de índice, lo que podría acelerar la búsqueda.

Cualquier sugerencia de ejemplos de código es muy bienvenida.

Gracias.

Answer 1

Sugeriría tratar de limitar el conjunto de resultados en algunos elementos y ver si el problema desaparece. Es decir, puede tener 5000 para elegir, pero trate de devolver como máximo 100, incluso si hay más coincidencias. Di:

var filterCollection = (from s in listCollection 
    where s.FilterValue.IndexOf(currentWord,StringComparison.OrdinalIgnoreCase)>=0 
    orderby s.FilterValue 
    select s).Take(100); 

Si el problema desaparece, la desaceleración puede ser causada por muchos artículos que son devueltos para el cuadro de lista. No estoy seguro de que el problema desaparezca, ya que el ListBox está virtualizado, pero vale la pena intentarlo. También puede intentar lo mismo, pero limitando el resultado del filtrado a 100 elementos, antes de ordenar (es decir, ordenar por) y ver si eso ayuda. Es más eficiente de hacerlo en este orden, de todos modos:

var filterCollection = (from s in listCollection 
    where s.FilterValue.IndexOf(currentWord,StringComparison.OrdinalIgnoreCase)>=0 
    select s).Take(100) 
      .OrderBy(s => s.FilterValue); 

El resultado final es determinar si el problema está en función del número de elementos devueltos y se asigna a filterColection o del número inicial de las partidas, o ambos .

Answer 2

Latencia no es su problema si tiene un conjunto de resultados de 2000 elementos. Estoy haciendo algunas suposiciones importantes aquí, pero solo necesita devolver 500 elementos como máximo: su usuario seguirá escribiendo para limitar el conjunto de resultados hasta que tenga un tamaño aceptable para examinar.

Debe optimizar el caso común (estoy asumiendo dónde terminará con decir ~ 50 elementos) - si su usuario está desplazándose a través de una pequeña lista de 2000 elementos, algo más está mal y la interfaz necesita más trabajo .

Answer 3

Una optimización realmente simple es

if(currentWord.StartsWith(lastWord)) 

puede filtrar la lista de elementos filtrados devueltos por la última consulta.Es decir, a menos que reduzca la cantidad de elementos devueltos por su consulta LINQ como lo sugieren algunas de las otras respuestas. Siempre puedes almacenar lo que hay en la consulta en una variable y luego hacer el Take (100) después, aunque necesitarás asegurarte de que la ejecución diferida de LINQ no te muerda en ese caso.

En el lado de encuadernación, en lugar de reemplazar toda la colección, puede usar un ObservableCollection y simplemente agregar/quitar elementos del mismo. Sería una buena idea invertir lo que devuelve tu filtro si vas a hacer eso, pero verías una respuesta mucho más rápida y no verías un rendimiento tan grande si el usuario está escribiendo rápidamente.

Answer 4

Creo que el problema es que su filtro realiza O(n) (donde n es el número total de elementos a partir de autocompletar), es decir, tiene que ir a través de cada artículo de averiguar cuáles partido. Cuantos más elementos tenga, peor será el filtro que realizará.

En lugar de utilizar una lista, intente con un trie. Intenta realizar O(m), donde m es el número de caracteres en la cadena. Esto significa que el tamaño del conjunto de datos no afecta el rendimiento de la búsqueda.

En Promptu (un iniciador de aplicaciones que escribí), utilizo try en intellisense/autocomplete. Si desea ver un ejemplo de intentos en acción, puede descargarlo y probarlo.

Answer 5

Aquí está su "condición de carrera".

orderby s.FilterValue 

Considere la secuencia de letras d, o, g.

• "d" comienza a funcionar y coincidirá con el 30% del conjunto. 6000 artículos deben ser ordenados.
• "do" comienza a funcionar y coincidirá con el 6% del conjunto. 1200 artículos deben ser ordenados.
• "perro" comienza a funcionar y coincidirá con el 0,5% del conjunto. 100 artículos deben ser ordenados

Al considerar las diferentes cargas de trabajo de cada evento, no es sorprendente que el último evento termine antes del primer y el segundo evento.

El comportamiento más correcto que puedo imaginar es evitar el enlace de cualquier evento activo anterior cuando se inicia un evento. Si puede evitar el enlace deteniendo la ejecución en esos eventos, mucho mejor. Recuerda esos misiles, ya no tienen objetivos.