La forma más rápida de buscar en una colección de cadenas

80

Problema:

Tengo un archivo de texto de alrededor de 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 se producirá cada vez que el usuario cambie el texto de a TextBoxy el resultado deben ser las cadenas que contienen el texto en formato TextBox.

No tengo que cambiar la lista, simplemente extraiga los resultados y póngalos en un archivo ListBox.

Lo que he probado hasta ahora:

Intenté con dos colecciones / contenedores diferentes, que estoy descargando las entradas de cadena de un archivo de texto externo (una vez, por supuesto):

  1. List<string> allUsers;
  2. 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?

etaiso
fuente
10
HashSet<T>no te ayudará aquí, porque estás buscando la parte de la cadena.
Dennis
8
Consulte las matrices de sufijos .
CodesInChaos
66
No pregunte "cuál es la forma más rápida de hacerlo", porque eso llevaría literalmente semanas o años de investigación. Más bien, diga "Necesito una solución que se ejecute en menos de 30 ms", o cualquiera que sea su objetivo de rendimiento. No necesita el dispositivo más rápido , necesita un dispositivo lo suficientemente rápido .
Eric Lippert
44
Además, obtenga un generador de perfiles . No adivine dónde está la parte lenta; tales suposiciones a menudo son incorrectas. El cuello de botella podría ser sorprendente.
Eric Lippert
4
@Basilevs: Una vez escribí una hermosa tabla hash O (1) que era extremadamente lenta en la práctica. Hice un perfil para averiguar por qué y descubrí que en cada búsqueda llamaba a un método que, no es broma, terminaba preguntando al registro "¿estamos en Tailandia ahora mismo?". No almacenar en caché si el usuario está en Tailandia fue el cuello de botella en ese código O (1). La ubicación del cuello de botella puede ser profundamente contradictoria . Usa un perfilador.
Eric Lippert

Respuestas:

48

Podría considerar realizar la tarea de filtrado en un hilo en segundo plano que invocaría un método de devolución de llamada cuando esté listo, o simplemente reiniciar el filtrado si se cambia 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 aproximado sería algo 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, debería eliminar la _filterinstancia cuando se elimine el padre Form. Esto significa que debe abrir y editar su Forms' Disposemétodo (dentro del YourForm.Designer.csarchivo) para buscar algo 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" posiblemente sería almacenar el último par de resultados en un diccionario, y luego filtrarlos únicamente si resulta que la nueva entrada difiere solo en el primero del último carácter.

Groo
fuente
¡Acabo de probar tu solución y funciona perfectamente! Bien hecho. El único problema que tengo es que no puedo _signal.Dispose();compilar (error sobre el nivel de protección).
etaiso
@etaiso: eso es raro, ¿dónde exactamente llamas? _signal.Dispose()¿Está fuera de la BackgroundWordFilterclase?
Groo
1
@Groo Es una implementación explícita, lo que significa que no puede llamarlo directamente. Se supone que debes usar un usingbloque o una llamadaWaitHandle.Close()
Matthew Watson
1
Bien, ahora tiene sentido, el método se hizo público en .NET 4. La página de MSDN para .NET 4 lo enumera bajo métodos públicos , mientras que la página para .NET 3.5 lo muestra bajo métodos protegidos . Eso también explica por qué hay una definición condicional en la fuente Mono para WaitHandle .
Groo
1
@Groo Lo siento, debería haber mencionado que estaba hablando de una versión anterior de .Net, ¡lo siento por la confusión! Sin embargo, tenga en cuenta que no necesita lanzar; en su .Close()lugar, puede llamar , lo que a su vez llama .Dispose().
Matthew Watson
36

Hice algunas pruebas, y buscar en una lista de 120.000 elementos y completar una nueva lista con las entradas lleva una cantidad de tiempo insignificante (aproximadamente 1/50 de segundo, incluso si todas las cadenas coinciden).

Por lo tanto, el problema que está viendo debe provenir del llenado de la fuente de datos, aquí:

listBox_choices.DataSource = ...

Sospecho que simplemente está poniendo demasiados elementos en el cuadro de lista.

Quizás 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 otros han señalado) que está accediendo a la TextBox.Textpropiedad 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, cronometré el tiempo que se tarda en acceder TextBox.Text500.000 veces y solo tomó 0,7 segundos, mucho menos que los 1-3 segundos mencionados en el OP. Aún así, esta es una optimización que vale la pena.

Matthew Watson
fuente
1
Gracias Matthew. Probé su solución, pero no creo que el problema esté en la población del ListBox. Creo que necesito un mejor enfoque ya que este tipo de filtrado es muy ingenuo (por ejemplo, la búsqueda de "abc" devuelve 0 resultados, entonces ni siquiera debería buscar "abcX", etc.)
etaiso
@etaiso correcto (incluso si la solución de Matthew puede funcionar muy bien si realmente no necesita preestablecer todas las coincidencias), es por eso que sugerí como segundo paso refinar la búsqueda en lugar de realizar una búsqueda completa cada vez.
Adriano Repetti
5
@etaiso Bueno, el tiempo de búsqueda es insignificante como dije. Lo probé con 120.000 cuerdas y busqué una cuerda muy larga que no arrojara coincidencias y una cuerda muy corta que diese muchas coincidencias, ambas en menos de 1/50 de segundo.
Matthew Watson
3
¿ textBox_search.TextContribuye una cantidad mensurable al tiempo? Obtener la Textpropiedad en un cuadro de texto una vez para cada una de las 120k cadenas probablemente envíe 120k mensajes a la ventana de control de edición.
Gabe
@Gabe Sí, lo hace. Vea mi respuesta para más detalles.
Andris
28

Usar árbol de sufijo como índice. O más bien, simplemente cree un diccionario ordenado que asocie cada sufijo de cada nombre con la lista de nombres correspondientes.

Para 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 la entrada del usuario "sujetador".

  1. Bisecar el diccionario en la entrada del usuario para encontrar la entrada del usuario o la posición donde podría ir. De esta manera encontramos "barbara" - última tecla más baja que "sujetador". Se llama límite inferior para "sujetador". La búsqueda llevará un tiempo logarítmico.
  2. Itere desde la clave encontrada en adelante hasta que la entrada del usuario ya no coincida. Esto daría "bram" -> Abram y "braham" -> Abraham.
  3. Concatenar el resultado de la iteración (Abram, Abraham) y generarlo.

Estos árboles están diseñados para una búsqueda rápida de subcadenas. Su rendimiento está cerca de O (log n). Creo que este enfoque funcionará lo suficientemente rápido como para ser utilizado directamente por el hilo de la GUI. Además, funcionará más rápido que la solución con subprocesos debido a la ausencia de sobrecarga de sincronización.

Basilevs
fuente
Por lo que sé, las matrices de sufijos suelen ser una mejor opción que los árboles de sufijos. Más fácil de implementar y menor uso de memoria.
CodesInChaos
Propongo SortedList, que es muy fácil de construir y mantener a costa de la sobrecarga de memoria que se puede minimizar al proporcionar capacidades de listas.
Basilevs
Además, parece que las matrices (y ST original) están diseñadas para manejar textos grandes, mientras que aquí tenemos una gran cantidad de fragmentos cortos, lo cual es una tarea diferente.
Basilevs
+1 para el buen enfoque, pero usaría un mapa hash o un árbol de búsqueda real en lugar de buscar manualmente una lista.
OrangeDog
¿Hay alguna ventaja de usar el árbol de sufijos en lugar del árbol de prefijos?
jnovacho
15

Necesita un motor de búsqueda de texto (como Lucene.Net ) o una base de datos (puede considerar uno integrado como SQL CE , SQLite , etc.). En otras palabras, necesita una búsqueda indexada. La búsqueda basada en hash no se aplica aquí, porque busca subcadena, mientras que la búsqueda basada en hash es adecuada para buscar el valor exacto.

De lo contrario, será una búsqueda iterativa que recorrerá la colección.

Dennis
fuente
La indexación es una búsqueda basada en hash. Simplemente agrega todas las subcadenas como claves en lugar de solo el valor.
OrangeDog
3
@OrangeDog: en desacuerdo. La búsqueda indexada se puede implementar como búsqueda basada en hash mediante claves de índice, pero no es necesaria y no es una búsqueda basada en hash por el valor de la cadena en sí.
Dennis
@Dennis de acuerdo. +1 para cancelar el fantasma -1.
usuario
+1 porque implementaciones como un motor de búsqueda de texto tienen optimizaciones (más) inteligentes que string.Contains. Es decir. buscar baen bcaaaabaaresultará en una lista (indexado) saltar. Se bconsidera el primero , pero no coincide porque el siguiente es un c, por lo que pasará al siguiente b.
Caramiriel
12

También puede ser útil tener un evento del tipo "antirrebote". Esto se diferencia de la limitación en que espera un período de tiempo (por ejemplo, 200 ms) a que finalicen los cambios antes de activar el evento.

Ver Debounce and Throttle: una explicación visual para obtener más información sobre el antirrebote. Aprecio que este artículo se centre en JavaScript, en lugar de C #, pero se aplica el principio.

La ventaja de esto es que no busca cuando todavía está ingresando su consulta. Entonces debería dejar de intentar realizar dos búsquedas a la vez.

paulslater19
fuente
Para ver una implementación en C # de un regulador de eventos, la clase EventThrotler en la biblioteca Algorithmia: github.com/SolutionsDesign/Algorithmia/blob/master/…
Frans Bouma
11

Ejecute la búsqueda en otro hilo y muestre alguna animación de carga o una barra de progreso mientras ese hilo se está ejecutando.

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);
}
animaonline
fuente
1
Sé que es una posibilidad. Pero mi pregunta aquí es si y cómo puedo acortar este proceso.
etaiso
1
@etaiso, en realidad no debería ser un problema a menos que esté desarrollando en un hardware de gama baja, asegúrese de no ejecutar el depurador, CTRL + F5
animaonline
1
Este no es un buen candidato para PLINQ ya que el método String.Containsno es caro. msdn.microsoft.com/en-us/library/dd997399.aspx
Tim Schmelter
1
@TimSchmelter cuando hablamos de toneladas de cadenas, ¡lo es!
animaonline
4
@TimSchmelter No tengo idea de lo que está tratando de probar, usar el código que proporcioné probablemente aumentará el rendimiento del OP, y aquí hay un punto de referencia que demuestra cómo funciona: pastebin.com/ATYa2BGt --- Punto - -
animaonline
11

Actualizar:

Hice algunos perfiles.

(Actualización 3)

  • Contenido de la lista: números generados de 0 a 2.499.999
  • Texto de filtro: 123 (20.477 resultados)
  • Core i5-2500, Win7 de 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 al textBox_search.Textinterior Contains. Esto hace una llamada para cada elemento al costoso get_WindowTextmétodo 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 son ahora la llamada a string.Contains(aproximadamente el 45% del tiempo de ejecución) y la actualización de los elementos del cuadro de lista en set_Datasource(30%).

Podríamos hacer un intercambio entre la velocidad y el uso de la memoria creando un árbol de sufijos como ha sugerido Basilevs para reducir el número de comparaciones necesarias y empujar un poco de tiempo de procesamiento desde la búsqueda después de presionar una tecla hasta la carga de los nombres del archivo que puede ser preferible para el usuario.

Para aumentar el rendimiento de la carga de 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 manera, le das una retroalimentación al usuario de que hay resultados disponibles para que pueda refinar su búsqueda ingresando más letras o cargar la lista completa con solo presionar un botón.

Utilizando BeginUpdatey EndUpdatesin cambios en el tiempo de ejecución de set_Datasource.

Como otros han señalado aquí, la consulta LINQ en sí se ejecuta bastante rápido. Creo que su cuello de botella es la actualización del cuadro de lista en sí. Puedes 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.

Andris
fuente
No creo que esto mejore nada, BeginUpdateya que EndUpdateestán destinados a usarse al agregar elementos individualmente o al usarlos AddRange().
etaiso
Depende de cómo DataSourcese implemente la propiedad. Podría valer la pena intentarlo.
Andris
Los resultados de su perfil son muy diferentes a los míos. Pude buscar 120k cadenas en 30 ms, pero agregarlas al cuadro de lista tomó 4500 ms. Parece que está agregando cadenas de 2.5M al cuadro de lista en menos de 600ms. ¿Cómo es eso posible?
Gabe
@Gabe Al crear perfiles, utilicé una entrada en la que el texto del filtro eliminó una gran parte de la lista original. Si utilizo una entrada en la que el texto del filtro no elimina nada de la lista, obtengo resultados similares a los suyos. Actualizaré mi respuesta para aclarar lo que he medido.
Andris
9

Suponiendo que solo coincide con prefijos, la estructura de datos que está buscando se llama trie , también conocida como "árbol de prefijos". El IEnumerable.Wheremétodo 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 #.

Groo
fuente
1
Suponiendo que esté filtrando sus registros con un prefijo.
Tarec
1
Observe que está usando el método String.Contains () en lugar de String.StartsWith (), por lo que puede que no sea exactamente lo que estamos buscando. Aún así, su idea es sin duda mejor que el filtrado ordinario con la extensión StartsWith () en el escenario de prefijo.
Tarec
Si quiere decir que comienza con, entonces el Trie se puede combinar con el enfoque del trabajador en segundo plano para mejorar el rendimiento
Lyndon White
8

El control WinForms ListBox realmente es su enemigo aquí. La carga de los registros será lenta y ScrollBar luchará contra usted para mostrar los 120,000 registros.

Intente usar un DataGridView antiguo derivado de datos en un DataTable con una sola columna [UserName] para almacenar 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;
}
LarsTech
fuente
2
+1 mientras todos los demás intentaban optimizar la búsqueda que solo toma 30 ms, usted es la única persona que reconoció que el problema está en completar el cuadro de lista.
Gabe
7

En primer lugar me gustaría cambiar la forma ListControlve el origen de datos, que está convirtiendo resultado IEnumerable<string>a List<string>. Especialmente cuando acaba de escribir pocos caracteres, esto puede ser ineficaz (e innecesario). No haga copias extensivas de sus datos .

  • Envolvería el .Where()resultado en una colección que implementa solo lo que se requiere de IList(búsqueda). Esto le evitará crear una nueva lista grande para cada carácter que se escriba.
  • 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 no tener que reasignarla para cada búsqueda.

El segundo paso es no buscar en la lista grande cuando una pequeña es suficiente. Cuando el usuario comenzó a escribir "ab" y agrega "c", entonces no necesita buscar en la lista grande, la búsqueda en la lista filtrada es suficiente (y más rápida). Refinar busqueda 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 que se puedan buscar rápidamente . Ahora tienes que cambiar la estructura que usas para almacenar tus datos. imagina un árbol como este:

A B C
 Agregue un mejor techo
 Encima del contorno del hueso

Esto puede implementarse simplemente con una matriz (si está trabajando con nombres ANSI, de lo contrario, sería mejor un diccionario). Cree la lista de esta manera (con fines ilustrativos, 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 omití la segunda sugerencia por brevedad, si elige el tamaño correcto para la clave del diccionario, puede mantener cada lista corta y rápida para, tal vez, evitar cualquier otra cosa). Además, tenga en cuenta que puede intentar utilizar los dos primeros caracteres para su diccionario (más listas y más corto). Si extiende esto, tendrá un árbol (pero no creo que tenga una cantidad tan grande 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 mediante la construcción de un autómata finito determinista (DFA) que reconoce la cadena de búsqueda almacenada. Estos son costosos de construir, por lo general se crean usando la construcción del conjunto de energía, pero son muy rápidos de usar.
  • Stubs : Knuth – Morris – Pratt calcula un DFA que reconoce las entradas con la cadena a buscar como sufijo, Boyer – Moore comienza a buscar desde el final de la aguja, por lo que normalmente puede avanzar 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 adapta 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 construir 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, están destinados a encontrar una puntuación de "cercanía" entre la cadena de búsqueda y el texto en lugar de una "coincidencia / no coincidencia". En ocasiones, se denominan búsquedas "difusas".

Pocas palabras sobre la búsqueda paralela. Es posible, pero rara vez es trivial porque la sobrecarga para hacerlo paralelo puede ser fácilmente mucho mayor que la búsqueda en sí. No realizaría la búsqueda en paralelo (la partición y la sincronización pronto se volverán demasiado expansivas y quizás complejas) pero movería la búsqueda a un hilo separado . Si el hilo principal no está ocupado, sus usuarios no sentirán ningún retraso mientras escriben (no notarán si la lista aparecerá después de 200 ms, pero se sentirán incómodos si tienen que esperar 50 ms después de escribir) . Por supuesto, la búsqueda en sí debe ser lo suficientemente rápida; en este caso, no utiliza subprocesos para acelerar la búsqueda sino para mantener la interfaz de usuario receptiva . consulta, no se bloqueará la interfaz de usuario, pero si su consulta fue lenta, seguirá siendo lenta en un hilo separado (además, también debe manejar múltiples solicitudes secuenciales).

Adriano Repetti
fuente
1
Como algunos ya han señalado, OP no quiere limitar los resultados solo a prefijos (es decir, usa Contains, no StartsWith). En una nota al margen, generalmente es mejor usar el ContainsKeymétodo genérico al buscar una clave para evitar el boxeo, e incluso mejor usarlo TryGetValuepara evitar dos búsquedas.
Groo
2
@Groo, tienes razón, como dije, es solo con fines ilustrativos. El punto de ese código no es una solución funcional, sino una pista: si probaste todo lo demás (evita copias, refina la búsqueda, muévelo a otro hilo) y no es suficiente, entonces tienes que cambiar la estructura de datos que estás usando . El ejemplo es para el comienzo de una cadena para ser simple.
Adriano Repetti
@Adriano ¡gracias por una respuesta clara y detallada! Estoy de acuerdo con la mayoría de las cosas que mencionaste, pero como dijo Groo, la última parte de mantener los datos organizados no es aplicable en mi caso. Pero creo que tal vez para tener un diccionario similar con claves como la letra contenida (aunque todavía habrá duplicados)
etaiso
después de una verificación y un cálculo rápidos, la idea de "letra contenida" no es buena para un solo carácter (y si optamos por combinaciones de dos o más, terminaremos con una tabla hash muy grande)
etaiso
@etaiso sí, puede mantener una lista de dos letras (para reducir rápidamente las sublistas) pero un árbol verdadero puede funcionar mejor (cada letra está vinculada a sus sucesoras, no importa dónde está dentro de la cadena, así que para "INICIO" tiene "H-> O", "O-> M" y "M-> E". Si estás buscando "om", lo encontrarás rápidamente. El problema es que se vuelve bastante más complicado y puede ser demasiado para su escenario (OMI).
Adriano Repetti
4

Puede intentar usar PLINQ (Parallel LINQ). Aunque esto no garantiza un aumento de velocidad, debe averiguarlo mediante prueba y error.

D. Gierveld
fuente
4

Dudo que puedas hacerlo más rápido, pero seguro que deberías:

a) Utilice el método de extensión AsParallel LINQ

a) Use algún tipo de temporizador para retrasar el filtrado

b) Ponga un método de filtrado en otro hilo

Guarde algún tipo de en string previousTextBoxValuealgún lugar. Haga un temporizador con un retraso de 1000 ms, que se active buscando en el tic si previousTextBoxValuees el mismo que su textbox.Textvalor. Si no es así, reasigne previousTextBoxValueal valor actual y reinicie el temporizador. Configure el inicio del temporizador para el evento de cambio de cuadro de texto y hará que su aplicación sea más fluida. Filtrar 120.000 registros en 1-3 segundos está bien, pero su interfaz de usuario debe seguir respondiendo.

Tarec
fuente
1
No estoy de acuerdo en hacerlo paralelo, pero estoy absolutamente de acuerdo con los otros dos puntos. Incluso puede ser suficiente para satisfacer los requisitos de la interfaz de usuario.
Adriano Repetti
Olvidé mencionar eso, pero estoy usando .NET 3.5, por lo que AsParallel no es una opción.
etaiso
3

También puede intentar usar la función BindingSource.Filter . Lo he usado y funciona como un encanto para filtrar de un montón de registros, cada vez que actualizo esta propiedad con el texto que se busca. Otra opción sería utilizar AutoCompleteSource para el control TextBox.

¡Espero eso ayude!

Nunca sin esperanza
fuente
2

Intentaría ordenar la colección, buscar para que coincida solo con la parte inicial y limitar la búsqueda por algún número.

así sucesivamente inicialización

allUsers.Sort();

y buscar

allUsers.Where(item => item.StartWith(textBox_search.Text))

Quizás puedas agregar algo de caché.

duro
fuente
1
No está trabajando con el comienzo de la cadena (por eso está usando String.Contains ()). Con Contains (), una lista ordenada no cambia el rendimiento.
Adriano Repetti
Sí, con 'Contiene' es inútil. Me gusta la sugerencia con el árbol de sufijos stackoverflow.com/a/21383731/994849 Hay muchas respuestas interesantes en el hilo, pero depende de cuánto tiempo pueda dedicar a esta tarea.
hardsky
1

Utilice Paralelo LINQ. PLINQes una implementación paralela de LINQ to Objects. PLINQ implementa el conjunto completo de operadores de consulta 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 legibilidad de la sintaxis LINQ con el poder de la programación paralela. Al igual que el código que se dirige a la biblioteca paralela de tareas, las consultas PLINQ se escalan en el grado de simultaneidad según las capacidades de la computadora host.

Introducción a PLINQ

Entendiendo Speedup en PLINQ

También puedes usar Lucene.Net

Lucene.Net es un puerto de la biblioteca del motor de búsqueda de 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:


fuente
1

Según lo que he visto estoy de acuerdo con el hecho de ordenar la lista.

Sin embargo, ordenar cuando se construya la lista será muy lento, ordenar al construir, tendrá un mejor tiempo de ejecución.

De lo contrario, si no necesita mostrar la lista o mantener el orden, use un mapa de hash.

El mapa de hash aplicará un hash a su cadena y buscará el desplazamiento exacto. Creo que debería ser más rápido.

dada
fuente
Hashmap con que clave? Quiero poder encontrar palabras clave que contengan las cadenas.
etaiso
para la tecla puedes poner el número en la lista, si quieres más complementos puedes agregar el número más el nombre, la elección es tuya.
dada
para el resto o no leí todo o hubo una mala explicación (probablemente ambos;)) [cita] tengo un archivo de texto de alrededor de 120.000 usuarios (cadenas) que me gustaría almacenar en una colección y luego realizar un buscar en esa colección. [/ quote] Pensé que era solo una búsqueda de cadenas.
dada
1

Intente 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 lento al agregar nuevos elementos, pero según tengo entendido, solo tiene un problema de rendimiento de búsqueda.

usuario2917540
fuente