c# - valid - La forma más rápida de buscar en una colección de cuerdas
tag c# (17)
Problema:
Tengo un archivo de texto de aproximadamente 120,000 usuarios (cadenas) que me gustaría almacenar en una colección y luego realizar una búsqueda en esa colección.
El método de búsqueda ocurrirá cada vez que el usuario cambie el texto de un TextBox y el resultado deberían ser las cadenas que contienen el texto en TextBox .
No tengo que cambiar la lista, simplemente extraer los resultados y ponerlos en un ListBox .
Lo que he intentado hasta ahora:
Intenté con dos colecciones / contenedores diferentes, que estoy volcando las entradas de cadena desde un archivo de texto externo (una vez, por supuesto):
-
List<string> allUsers; -
HashSet<string> allUsers;
Con la siguiente consulta LINQ :
allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
Mi evento de búsqueda (se activa cuando el usuario cambia el texto de búsqueda):
private void textBox_search_TextChanged(object sender, EventArgs e)
{
if (textBox_search.Text.Length > 2)
{
listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
}
else
{
listBox_choices.DataSource = null;
}
}
Resultados:
Ambos me dieron un tiempo de respuesta pobre (alrededor de 1-3 segundos entre cada pulsación de tecla).
Pregunta:
¿Dónde crees que está mi cuello de botella? La colección que he usado? El método de búsqueda? ¿Ambos?
¿Cómo puedo obtener un mejor rendimiento y una funcionalidad más fluida?
Actualizar:
Hice algunos perfiles.
(Actualización 3)
- Contenido de la lista: números generados de 0 a 2.499.999
- Texto del filtro: 123 (20.477 resultados)
- Core i5-2500, Win7 64 bits, 8 GB de RAM
- VS2012 + JetBrains dotTrace
La prueba inicial de 2.500.000 registros me llevó 20.000ms.
El culpable número uno es la llamada a textBox_search.Text inside Contains . Esto hace una llamada para cada elemento al costoso método get_WindowText del cuadro de texto. Simplemente cambiando el código a:
var text = textBox_search.Text;
listBox_choices.DataSource = allUsers.Where(item => item.Contains(text)).ToList();
redujo el tiempo de ejecución a 1.858ms .
Actualización 2:
Los otros dos cuellos de botella importantes ahora son la llamada a la string.Contains . string.Contains (aproximadamente el 45% del tiempo de ejecución) y la actualización de los elementos de la lista en set_Datasource (30%).
Podríamos hacer un intercambio entre la velocidad y el uso de la memoria creando un árbol de Sufijo, ya que Basilevs sugirió reducir el número de comparaciones necesarias e impulsar algún tiempo de procesamiento desde la búsqueda después de presionar una tecla hasta cargar los nombres del archivo que podría ser preferible para el usuario.
Para aumentar el rendimiento de cargar los elementos en el cuadro de lista, sugeriría cargar solo los primeros elementos e indicar al usuario que hay más elementos disponibles. De esta forma, le das una retroalimentación al usuario de que hay resultados disponibles para que pueda refinar su búsqueda ingresando más letras o cargando la lista completa con solo presionar un botón.
El uso de BeginUpdate y EndUpdate no modificó el tiempo de ejecución de set_Datasource .
Como otros han notado aquí, la consulta LINQ en sí funciona bastante rápido. Creo que su cuello de botella es la actualización del cuadro de lista en sí. Podrías probar algo como:
if (textBox_search.Text.Length > 2)
{
listBox_choices.BeginUpdate();
listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
listBox_choices.EndUpdate();
}
Espero que esto ayude.
De acuerdo con lo que he visto, estoy de acuerdo con el hecho de ordenar la lista.
Sin embargo, para ordenar cuando la lista es construir será muy lenta, ordena al construir, tendrás un mejor tiempo de ejecución.
De lo contrario, si no necesita mostrar la lista o mantener el orden, use un hashmap.
El hashmap hará un hash de su cadena y buscará el desplazamiento exacto. Debería ser más rápido, creo.
Dudo que puedas hacerlo más rápido, pero de seguro deberías:
a) Utilice el método de extensión AsParallel LINQ
a) Utiliza algún tipo de temporizador para retrasar el filtrado
b) Ponga un método de filtrado en otro hilo
Mantenga algún tipo de string previousTextBoxValue alguna parte. Crea un temporizador con un retraso de 1000 ms, que activa la búsqueda en tick si previousTextBoxValue es igual que tu textbox.Text . Valor del texto. De lo contrario, reasigne previousTextBoxValue al valor actual y reinicie el temporizador. Configure el inicio del temporizador para el evento modificado de la caja de texto, y hará que su aplicación sea más suave. Filtrar 120,000 registros en 1-3 segundos está bien, pero su UI debe seguir siendo receptiva.
Ejecute la búsqueda en otro subproceso y muestre alguna animación de carga o una barra de progreso mientras se está ejecutando ese subproceso.
También puede intentar paralelizar la consulta LINQ .
var queryResults = strings.AsParallel().Where(item => item.Contains("1")).ToList();
Aquí hay un punto de referencia que demuestra las ventajas de rendimiento de AsParallel ():
{
IEnumerable<string> queryResults;
bool useParallel = true;
var strings = new List<string>();
for (int i = 0; i < 2500000; i++)
strings.Add(i.ToString());
var stp = new Stopwatch();
stp.Start();
if (useParallel)
queryResults = strings.AsParallel().Where(item => item.Contains("1")).ToList();
else
queryResults = strings.Where(item => item.Contains("1")).ToList();
stp.Stop();
Console.WriteLine("useParallel: {0}/r/nTime Elapsed: {1}", useParallel, stp.ElapsedMilliseconds);
}
El control WinForms ListBox realmente es tu enemigo aquí. Tardará en cargar los registros y ScrollBar luchará contra usted para mostrar los 120,000 registros.
Intente utilizar datos DataGridView pasados de moda a una DataTable con una sola columna [UserName] para contener sus datos:
private DataTable dt;
public Form1() {
InitializeComponent();
dt = new DataTable();
dt.Columns.Add("UserName");
for (int i = 0; i < 120000; ++i){
DataRow dr = dt.NewRow();
dr[0] = "user" + i.ToString();
dt.Rows.Add(dr);
}
dgv.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.Fill;
dgv.AllowUserToAddRows = false;
dgv.AllowUserToDeleteRows = false;
dgv.RowHeadersVisible = false;
dgv.DataSource = dt;
}
Luego use un DataView en el evento TextChanged de su TextBox para filtrar los datos:
private void textBox1_TextChanged(object sender, EventArgs e) {
DataView dv = new DataView(dt);
dv.RowFilter = string.Format("[UserName] LIKE ''%{0}%''", textBox1.Text);
dgv.DataSource = dv;
}
Hice algunas pruebas, y buscar una lista de 120,000 elementos y completar una nueva lista con las entradas lleva una cantidad insignificante de tiempo (aproximadamente una 1/50 parte de un segundo, incluso si todas las cadenas coinciden).
Por lo tanto, el problema que está viendo debe provenir del poblado de la fuente de datos, aquí:
listBox_choices.DataSource = ...
Sospecho que simplemente está poniendo demasiados elementos en el cuadro de lista.
Tal vez deberías intentar limitarlo a las primeras 20 entradas, así:
listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text))
.Take(20).ToList();
También tenga en cuenta (como han señalado otros) que está accediendo a la propiedad TextBox.Text para cada elemento en allUsers . Esto se puede solucionar fácilmente de la siguiente manera:
string target = textBox_search.Text;
listBox_choices.DataSource = allUsers.Where(item => item.Contains(target))
.Take(20).ToList();
Sin embargo, TextBox.Text tiempo que lleva acceder a TextBox.Text 500,000 veces y solo tomó 0.7 segundos, mucho menos que los TextBox.Text segundos mencionados en el OP. Aún así, esta es una optimización que vale la pena.
Intentaré ordenar la recopilación, búsqueda para que coincida solo con comenzar la búsqueda de parte y límite por algún número.
etc. en la inicialización
allUsers.Sort();
y búsqueda
allUsers.Where(item => item.StartWith(textBox_search.Text))
Quizás puedas agregar algo de caché.
Necesita un motor de búsqueda de texto (como Lucene.Net ) o una base de datos (puede considerar uno incrustado como SQL CE , SQLite , etc.). En otras palabras, necesita una búsqueda indexada. La búsqueda basada en hash no es aplicable aquí, porque estás buscando una subcadena, mientras que la búsqueda basada en hash es adecuada para buscar el valor exacto.
De lo contrario, será una búsqueda iterativa con un bucle a través de la colección.
Podría considerar realizar la tarea de filtrado en un hilo de fondo que invocaría un método de devolución de llamada cuando esté terminado, o simplemente reiniciar el filtrado si se modifica la entrada.
La idea general es poder usarlo así:
public partial class YourForm : Form
{
private readonly BackgroundWordFilter _filter;
public YourForm()
{
InitializeComponent();
// setup the background worker to return no more than 10 items,
// and to set ListBox.DataSource when results are ready
_filter = new BackgroundWordFilter
(
items: GetDictionaryItems(),
maxItemsToMatch: 10,
callback: results =>
this.Invoke(new Action(() => listBox_choices.DataSource = results))
);
}
private void textBox_search_TextChanged(object sender, EventArgs e)
{
// this will update the background worker''s "current entry"
_filter.SetCurrentEntry(textBox_search.Text);
}
}
Un boceto sería algo así como:
public class BackgroundWordFilter : IDisposable
{
private readonly List<string> _items;
private readonly AutoResetEvent _signal = new AutoResetEvent(false);
private readonly Thread _workerThread;
private readonly int _maxItemsToMatch;
private readonly Action<List<string>> _callback;
private volatile bool _shouldRun = true;
private volatile string _currentEntry = null;
public BackgroundWordFilter(
List<string> items,
int maxItemsToMatch,
Action<List<string>> callback)
{
_items = items;
_callback = callback;
_maxItemsToMatch = maxItemsToMatch;
// start the long-lived backgroud thread
_workerThread = new Thread(WorkerLoop)
{
IsBackground = true,
Priority = ThreadPriority.BelowNormal
};
_workerThread.Start();
}
public void SetCurrentEntry(string currentEntry)
{
// set the current entry and signal the worker thread
_currentEntry = currentEntry;
_signal.Set();
}
void WorkerLoop()
{
while (_shouldRun)
{
// wait here until there is a new entry
_signal.WaitOne();
if (!_shouldRun)
return;
var entry = _currentEntry;
var results = new List<string>();
// if there is nothing to process,
// return an empty list
if (string.IsNullOrEmpty(entry))
{
_callback(results);
continue;
}
// do the search in a for-loop to
// allow early termination when current entry
// is changed on a different thread
foreach (var i in _items)
{
// if matched, add to the list of results
if (i.Contains(entry))
results.Add(i);
// check if the current entry was updated in the meantime,
// or we found enough items
if (entry != _currentEntry || results.Count >= _maxItemsToMatch)
break;
}
if (entry == _currentEntry)
_callback(results);
}
}
public void Dispose()
{
// we are using AutoResetEvent and a background thread
// and therefore must dispose it explicitly
Dispose(true);
}
private void Dispose(bool disposing)
{
if (!disposing)
return;
// shutdown the thread
if (_workerThread.IsAlive)
{
_shouldRun = false;
_currentEntry = null;
_signal.Set();
_workerThread.Join();
}
// if targetting .NET 3.5 or older, we have to
// use the explicit IDisposable implementation
(_signal as IDisposable).Dispose();
}
}
Además, en realidad debería deshacerse de la instancia de _filter cuando se _filter el Form principal. Esto significa que debe abrir y editar el método Dispose su Form (dentro del archivo YourForm.Designer.cs ) para que se vea algo así como:
// inside "xxxxxx.Designer.cs"
protected override void Dispose(bool disposing)
{
if (disposing)
{
if (_filter != null)
_filter.Dispose();
// this part is added by Visual Studio designer
if (components != null)
components.Dispose();
}
base.Dispose(disposing);
}
En mi máquina, funciona bastante rápido, por lo que debe probar y perfilar esto antes de buscar una solución más compleja.
Dicho esto, una "solución más compleja" sería almacenar los últimos resultados en un diccionario, y luego solo filtrarlos si resulta que la nueva entrada difiere solo por el primero del último carácter.
Podría intentar usar PLINQ (Parallel LINQ). Aunque esto no garantiza un aumento de velocidad, debe averiguarlo por prueba y error.
Primero, cambiaría la forma en que ListControl ve su fuente de datos, está convirtiendo el resultado IEnumerable<string> en List<string> . Especialmente cuando solo escribe algunos caracteres, esto puede ser ineficiente (e innecesario). No hagas copias expansivas de tus datos .
- Me gustaría envolver
.Where()resultado a una colección que implementa solo lo que se requiere deIList(búsqueda). Esto te ahorrará crear una nueva lista grande para cada personaje que se escribe. - Como alternativa, evitaría LINQ y escribiría algo más específico (y optimizado). Mantenga su lista en la memoria y cree una matriz de índices coincidentes, reutilice la matriz para que no tenga que reasignarla para cada búsqueda.
El segundo paso es no buscar en la lista grande cuando el pequeño es suficiente. Cuando el usuario comenzó a escribir "ab" y agrega "c", no necesita buscar en la lista grande, buscar en la lista filtrada es suficiente (y más rápido). Refine la búsqueda cada vez que sea posible, no realice una búsqueda completa cada vez.
El tercer paso puede ser más difícil: mantenga los datos organizados para una búsqueda rápida . Ahora debe cambiar la estructura que usa para almacenar sus datos. imagina un árbol como este:
A B C Add Better Ceil Above Bone Contour
Esto simplemente se puede implementar con una matriz (si está trabajando con nombres ANSI, de lo contrario, un diccionario sería mejor). Cree la lista de esta manera (fines de ilustración, coincide con el comienzo de la cadena):
var dictionary = new Dictionary<char, List<string>>();
foreach (var user in users)
{
char letter = user[0];
if (dictionary.Contains(letter))
dictionary[letter].Add(user);
else
{
var newList = new List<string>();
newList.Add(user);
dictionary.Add(letter, newList);
}
}
La búsqueda se realizará utilizando el primer carácter:
char letter = textBox_search.Text[0];
if (dictionary.Contains(letter))
{
listBox_choices.DataSource =
new MyListWrapper(dictionary[letter].Where(x => x.Contains(textBox_search.Text)));
}
Tenga en cuenta que utilicé MyListWrapper() como se sugirió en el primer paso (pero lo omití en la segunda sugerencia para abreviar, si elige el tamaño correcto para la clave del diccionario, puede mantener cada lista corta y rápida, tal vez, evitar cualquier otra cosa). Además, tenga en cuenta que puede intentar usar los dos primeros caracteres para su diccionario (más listas y más cortas). Si extiendes esto, tendrás un árbol (pero no creo que tengas una gran cantidad de elementos).
Hay muchos algoritmos diferentes para la búsqueda de cadenas (con estructuras de datos relacionadas), solo por mencionar algunos:
- Búsqueda basada en autómatas de estado finito : en este enfoque, evitamos retroceder construyendo un autómata finito determinista (DFA) que reconoce la cadena de búsqueda almacenada. Estos son costosos de construir, generalmente se crean usando la construcción de powerset, pero son muy rápidos de usar.
- Stubs : Knuth-Morris-Pratt calcula un DFA que reconoce las entradas con la cadena que se busca como sufijo, Boyer-Moore comienza a buscar desde el final de la aguja, por lo que generalmente puede saltar una longitud de aguja completa en cada paso. Baeza-Yates realiza un seguimiento de si los caracteres j anteriores eran un prefijo de la cadena de búsqueda y, por lo tanto, se puede adaptar a la búsqueda de cadenas difusas. El algoritmo bitap es una aplicación del enfoque de Baeza-Yates.
- Métodos de índice : los algoritmos de búsqueda más rápidos se basan en el preprocesamiento del texto. Después de crear un índice de subcadena, por ejemplo, un árbol de sufijos o una matriz de sufijos, las ocurrencias de un patrón se pueden encontrar rápidamente.
- Otras variantes : algunos métodos de búsqueda, por ejemplo, la búsqueda de trigramas, tienen como objetivo encontrar una puntuación de "cercanía" entre la cadena de búsqueda y el texto en lugar de una "coincidencia / no coincidencia". Estas a veces se llaman búsquedas "borrosas".
Pocas palabras sobre búsqueda paralela. Es posible, pero rara vez es trivial porque la sobrecarga para que sea paralela puede ser mucho más alta que la búsqueda en sí misma. No realizaría la búsqueda en paralelo (la partición y la sincronización pronto serán demasiado extensas y tal vez complejas) pero movería la búsqueda a un hilo por separado . Si el hilo principal no está ocupado, sus usuarios no sentirán ninguna demora mientras escriben (no se darán cuenta si la lista aparecerá después de 200 ms, pero se sentirán incómodos si tienen que esperar 50 ms después de que escribieron) . Por supuesto, la búsqueda en sí misma debe ser lo suficientemente rápida, en este caso usted no usa hilos para acelerar la búsqueda, sino para mantener su UI receptiva . Tenga en cuenta que un hilo separado no hará que su consulta sea más rápida , no se bloqueará la interfaz de usuario, pero si su consulta fue lenta, seguirá siendo lenta en un hilo separado (además, debe manejar múltiples solicitudes secuenciales también).
Suponiendo que solo está haciendo coincidir los prefijos, la estructura de datos que está buscando se llama trie , también conocida como "árbol de prefijos". El método IEnumerable.Where que está utilizando ahora tendrá que recorrer todos los elementos de su diccionario en cada acceso.
Este hilo muestra cómo crear un trie en C #.
También podría ser útil tener un tipo de evento "antirrebote". Esto difiere de la regulación en que espera un período de tiempo (por ejemplo, 200 ms) para que los cambios finalicen antes de disparar el evento.
Consulte Debounce and Throttle: una explicación visual para obtener más información sobre antirrebote. Aprecio que este artículo esté enfocado en JavaScript, en lugar de C #, pero se aplica el principio.
La ventaja de esto es que no realiza búsquedas cuando todavía está ingresando su consulta. Entonces debería dejar de intentar realizar dos búsquedas a la vez.
También puede intentar usar la función BindingSource.Filter . Lo he usado y funciona como un amuleto para filtrar desde un montón de registros, cada vez que actualice esta propiedad con el texto que está buscando. Otra opción sería usar AutoCompleteSource para control TextBox.
¡Espero eso ayude!
Usa Parallel LINQ . PLINQ es una implementación paralela de LINQ to Objects. PLINQ implementa el conjunto completo de operadores de consultas estándar LINQ como métodos de extensión para el espacio de nombres T: System.Linq y tiene operadores adicionales para operaciones paralelas. PLINQ combina la simplicidad y la legibilidad de la sintaxis LINQ con la potencia de la programación en paralelo. Al igual que el código que se dirige a la Biblioteca de tareas paralelas, las consultas PLINQ escalan en el grado de concurrencia según las capacidades de la computadora host.
También puedes usar Lucene.Net
Lucene.Net es un puerto de la biblioteca del motor de búsqueda Lucene, escrito en C # y dirigido a usuarios de tiempo de ejecución de .NET. La biblioteca de búsqueda de Lucene se basa en un índice invertido. Lucene.Net tiene tres objetivos principales:
Use el sufijo tree como índice. O mejor construya un diccionario ordenado que asocie cada sufijo de cada nombre con la lista de nombres correspondientes.
Para la entrada:
Abraham
Barbara
Abram
La estructura se vería así:
a -> Barbara
ab -> Abram
abraham -> Abraham
abram -> Abram
am -> Abraham, Abram
aham -> Abraham
ara -> Barbara
arbara -> Barbara
bara -> Barbara
barbara -> Barbara
bram -> Abram
braham -> Abraham
ham -> Abraham
m -> Abraham, Abram
raham -> Abraham
ram -> Abram
rbara -> Barbara
Algoritmo de búsqueda
Suponga que el usuario ingresa "bra".
- Bisect el diccionario en la entrada del usuario para encontrar la entrada del usuario o la posición donde podría ir. De esta forma, encontramos "barbara", la última clave más baja que "bra". Se llama límite inferior para "sujetador". La búsqueda tomará tiempo logarítmico.
- Iterar desde la tecla encontrada en adelante hasta que la entrada del usuario ya no coincida. Esto daría "bram" -> Abram y "braham" -> Abraham.
- Concatenar el resultado de la iteración (Abram, Abraham) y darlo a luz.
Dichos árboles están diseñados para una búsqueda rápida de subcadenas. Su rendimiento es cercano a O (log n). Creo que este enfoque funcionará lo suficientemente rápido como para ser utilizado directamente por el hilo de GUI. Además, funcionará más rápido que la solución roscada debido a la ausencia de sobrecarga de sincronización.
Intenta usar el método BinarySearch, debería funcionar más rápido que el método Contiene.
Contiene será un O (n) BinarySearch es un O (lg (n))
Creo que la colección ordenada debería funcionar más rápido en la búsqueda y más lenta en la adición de elementos nuevos, pero como entendí, solo tienes un problema en el rendimiento de la búsqueda.