79 votes

Moyen le plus rapide de rechercher dans une collection de chaînes

Problème:

J'ai un fichier texte de près de 120 000 utilisateurs (chaînes de caractères) que je voudrais stocker dans une collection, et plus tard pour effectuer une recherche sur cette collection.

La méthode de recherche se produit chaque fois que l'utilisateur de modifier le texte d'un TextBox et le résultat devrait être les chaînes de caractères qui contiennent le texte en TextBox.

Je n'ai pas à modifier la liste, il suffit de tirer les résultats et les mettre dans un ListBox.

Ce que j'ai essayé jusqu'à présent:

J'ai essayé avec deux collections différentes des conteneurs, dont je suis un dumping de la chaîne d'entrées à partir d'un fichier texte externe (une fois, bien sûr):

  1. List<string> allUsers;
  2. HashSet<string> allUsers;

À la suite de LINQ requête:

allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();

Ma recherche de l'événement (se déclenche lorsque l'utilisateur de modifier le texte de la recherche):

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;
    }
}

Résultats:

Tous deux m'ont donné une mauvaise réponse en temps (environ 1 à 3 secondes entre chaque pression sur la touche).

Question:

Où pensez-vous de mon goulot d'étranglement est? La collection que j'ai utilisé? La méthode de recherche? Les deux?

Comment puis-je obtenir les meilleures performances et plus fluide de la fonctionnalité?

48voto

Groo Points 19453

Vous pourriez envisager de faire du filtrage de tâche sur un thread d'arrière-plan qui permettrait d'invoquer une méthode de rappel lorsque c'est fait, ou tout simplement redémarrer le filtrage si l'entrée est changé.

L'idée générale est d'être capable de l'utiliser comme ceci:

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 croquis serait quelque chose comme:

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();
    }
}

Aussi, vous devriez vraiment jeter l' _filter exemple, lorsque le parent Form sont éliminés. Cela signifie que vous devez ouvrir et d'éditer vos Forms' Dispose méthode (à l'intérieur de l' YourForm.Designer.cs fiche) pour ressembler à quelque chose comme:

// 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);
}

Sur ma machine, il fonctionne très rapidement, de sorte que vous devez tester et profil avant d'aller pour une solution complexe.

Cela étant dit, un "plus complexe solution" serait peut-être à stocker le dernier couple de résultats dans un dictionnaire, puis filtrer uniquement si il s'avère que la nouvelle entrée diffère que par la première du dernier caractère.

36voto

Matthew Watson Points 30804

J'ai fait quelques tests, et la recherche d'une liste de 120 000 articles et remplissage d'une nouvelle liste avec les entrées prend une quantité négligeable de temps (environ 1/50ème de seconde, même si toutes les cordes sont appariés).

Le problème que vous voyez doit donc venir de la population de la source de données, ici:

listBox_choices.DataSource = ...

Je soupçonne que vous êtes tout simplement en mettant trop d'éléments dans la zone de liste.

Peut-être que vous devriez essayer de la limiter à la première de 20 entrées, comme suit:

listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text))
    .Take(20).ToList();

Notez aussi (comme d'autres l'ont souligné) que vous accédez à l' TextBox.Text de la propriété pour chaque élément en allUsers. Cela peut facilement être fixé comme suit:

string target = textBox_search.Text;
listBox_choices.DataSource = allUsers.Where(item => item.Contains(target))
    .Take(20).ToList();

Cependant, j'ai chronométré combien de temps il faut pour accéder TextBox.Text de 500 000 fois et il a seulement pris de 0,7 secondes, beaucoup moins que les 1 - 3 secondes mentionné dans l'OP. Pourtant, cela vaut la peine d'optimisation.

28voto

Basilevs Points 4048

Utiliser le Suffixe de l'arbre comme index. Ou plutôt à construire une triés dictionnaire qui associe à chaque suffixe de chaque nom de la liste des noms correspondants.

Pour l'entrée:

Abraham
Barbara
Abram

La structure ressemblerait à:

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

Algorithme de recherche

Supposons que l'utilisateur d'entrée "soutien-gorge".

  1. Traversent le dictionnaire sur la saisie de l'utilisateur à trouver l'entrée de l'utilisateur ou de la position où il pourrait aller. De cette façon, nous trouvons "barbara" - dernière touche est inférieur au "soutien-gorge". Il est appelé limite inférieure pour "soutien-gorge". La recherche prendra du temps logarithmique.
  2. Itération de la trouvé la clé jusqu'à ce que la saisie de l'utilisateur ne correspond plus. Ce serait donner "bram" -> Abram et "braham" -> Abraham.
  3. Concaténer itération résultat (Abram, Abraham) et de sortie.

Ces arbres sont conçus pour en faciliter la recherche de sous-chaînes. Ce rendement est proche de O(log n). Je crois que cette approche permettra de travailler assez vite pour être utilisé par thread GUI directement. En outre, il permettra de travailler plus vite enfilées solution en raison de l'absence de la surcharge de la synchronisation.

15voto

Dennis Points 14573

Vous avez besoin d'un moteur de recherche de texte (comme Lucene.Net), ou de la base de données (vous pouvez envisager un imbriqués les uns comme SQL CE, SQLite,...). En d'autres termes, vous avez besoin d'une recherche indexée. De hachage la fonction de recherche n'est pas applicable ici, parce que vous la recherche de sous-chaîne, tandis que de hachage la fonction de recherche est bien pour la recherche de la valeur exacte.

Sinon il va être un processus itératif de recherche avec boucle à travers la collection.

12voto

paulslater19 Points 3125

Il pourrait également être utile d'avoir un "anti-rebond" type d'événement. Cela diffère de la limitation en ce qu'il attend d'une période de temps (par exemple, 200 ms) pour les changements avant la fin de la cuisson de l'événement.

Voir anti-rebond et la manette des Gaz: une explication visuelle pour plus d'informations à propos de l'anti-rebond. J'apprécie le fait que cet article est JavaScript porté, au lieu de C#, mais le principe s'applique.

L'avantage, c'est que ça ne fait pas de recherche lorsque vous êtes encore entrer votre requête. Ensuite, elle devrait arrêter d'essayer d'effectuer deux recherches à la fois.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X