Schnellster Weg, um in einer String-Sammlung zu suchen

80

Problem:

Ich habe eine Textdatei mit ungefähr 120.000 Benutzern (Zeichenfolgen), die ich in einer Sammlung speichern und später eine Suche in dieser Sammlung durchführen möchte.

Die Suchmethode wird jedes Mal ausgeführt, wenn der Benutzer den Text von a ändert. Das TextBoxErgebnis sollten die Zeichenfolgen sein, in denen der Text enthalten istTextBox .

Ich muss die Liste nicht ändern, sondern nur die Ergebnisse abrufen und in eine Liste einfügen ListBox.

Was ich bisher versucht habe:

Ich habe es mit zwei verschiedenen Sammlungen / Containern versucht, bei denen ich die Zeichenfolgeneinträge aus einer externen Textdatei entleere (natürlich einmal):

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

Mit der folgenden LINQ- Abfrage:

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

Mein Suchereignis (wird ausgelöst, wenn der Benutzer den Suchtext ändert):

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

Ergebnisse:

Beide gaben mir eine schlechte Reaktionszeit (ca. 1-3 Sekunden zwischen jedem Tastendruck).

Frage:

Wo denkst du ist mein Engpass? Die Sammlung, die ich benutzt habe? Die Suchmethode? Beide?

Wie kann ich eine bessere Leistung und flüssigere Funktionalität erzielen?

etaiso
quelle
10
HashSet<T>wird Ihnen hier nicht helfen, weil Sie den Teil der Zeichenfolge suchen .
Dennis
8
Schauen Sie sich die Suffix-Arrays an .
CodesInChaos
66
Fragen Sie nicht nach dem schnellsten Weg, denn das würde buchstäblich Wochen bis Jahre dauern. Sagen Sie stattdessen "Ich brauche eine Lösung, die in weniger als 30 ms ausgeführt wird" oder was auch immer Ihr Leistungsziel ist. Sie brauchen nicht das schnellste Gerät, Sie brauchen ein ausreichend schnelles Gerät.
Eric Lippert
44
Holen Sie sich auch einen Profiler . Nicht erraten darüber , wo der langsame Teil ist; solche Vermutungen sind oft falsch. Der Engpass könnte irgendwo überraschend sein.
Eric Lippert
4
@Basilevs: Ich habe einmal eine schöne O (1) Hash-Tabelle geschrieben, die in der Praxis extrem langsam war. Ich profilierte es, um herauszufinden, warum und stellte fest, dass es bei jeder Suche eine Methode aufrief, die - kein Scherz - die Registrierung fragte: "Sind wir gerade in Thailand?". Das Nicht-Zwischenspeichern, ob sich der Benutzer in Thailand befindet, war der Engpass in diesem O (1) -Code. Die Lage des Engpasses kann zutiefst uninteressant sein . Verwenden Sie einen Profiler.
Eric Lippert

Antworten:

48

Sie können die Filteraufgabe für einen Hintergrundthread ausführen, der nach Abschluss eine Rückrufmethode aufruft, oder die Filterung einfach neu starten, wenn die Eingabe geändert wird.

Die allgemeine Idee ist, es so verwenden zu können:

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

Eine grobe Skizze wäre ungefähr so:

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

Außerdem sollten Sie die _filterInstanz tatsächlich entsorgen, wenn das übergeordnete FormElement entsorgt wird. Dies bedeutet , sollten Sie öffnen und bearbeiten Sie Ihre Form‚s - DisposeMethode (in der YourForm.Designer.csDatei) in etwa so aussehen:

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

Auf meinem Computer funktioniert es ziemlich schnell, daher sollten Sie dies testen und profilieren, bevor Sie sich für eine komplexere Lösung entscheiden.

Eine "komplexere Lösung" wäre jedoch möglicherweise, die letzten Ergebnisse in einem Wörterbuch zu speichern und sie dann nur zu filtern, wenn sich herausstellt, dass sich der neue Eintrag nur durch das erste oder letzte Zeichen unterscheidet.

Groo
quelle
Ich habe gerade Ihre Lösung getestet und sie funktioniert perfekt! Schön gemacht. Das einzige Problem, das ich habe, ist, dass ich das nicht _signal.Dispose();kompilieren kann (Fehler bezüglich der Schutzstufe).
Etaiso
@etaiso: das ist komisch, wo genau du anrufst _signal.Dispose()Ist es irgendwo außerhalb der BackgroundWordFilterKlasse?
Groo
1
@Groo Es ist eine explizite Implementierung, dh Sie können es nicht direkt aufrufen. Sie sollten entweder einen usingBlock verwenden oder anrufenWaitHandle.Close()
Matthew Watson
1
Ok, jetzt ist es sinnvoll, dass die Methode in .NET 4 veröffentlicht wurde. Die MSDN-Seite für .NET 4 listet sie unter öffentlichen Methoden auf , während die Seite für .NET 3.5 sie unter geschützten Methoden anzeigt . Dies erklärt auch, warum es in der Mono-Quelle eine bedingte Definition für WaitHandle gibt .
Groo
1
@Groo Entschuldigung, ich hätte erwähnen sollen, dass ich über eine ältere Version von .Net gesprochen habe - Entschuldigung für die Verwirrung! Beachten Sie jedoch, dass er nicht wirken muss - er kann .Close()stattdessen anrufen , was selbst anruft .Dispose().
Matthew Watson
36

Ich habe einige Tests durchgeführt, und das Durchsuchen einer Liste mit 120.000 Elementen und das Auffüllen einer neuen Liste mit den Einträgen dauert vernachlässigbar lange (etwa eine 1 / 50stel Sekunde, selbst wenn alle Zeichenfolgen übereinstimmen).

Das Problem, das Sie sehen, muss daher aus dem Auffüllen der Datenquelle stammen:

listBox_choices.DataSource = ...

Ich vermute, Sie legen einfach zu viele Elemente in die Listbox.

Vielleicht sollten Sie versuchen, es auf die ersten 20 Einträge zu beschränken, wie folgt:

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

Beachten Sie auch (wie andere bereits betont haben), dass Sie TextBox.Textfür jedes Element in auf die Eigenschaft zugreifen allUsers. Dies kann leicht wie folgt behoben werden:

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

Ich habe jedoch festgelegt, wie lange der Zugriff TextBox.Text500.000 Mal dauert, und es hat nur 0,7 Sekunden gedauert, weit weniger als die im OP genannten 1 - 3 Sekunden. Dies ist jedoch eine lohnende Optimierung.

Matthew Watson
quelle
1
Danke Matthew. Ich habe Ihre Lösung ausprobiert, aber ich glaube nicht, dass das Problem bei der Bevölkerung der ListBox liegt. Ich denke, dass ich einen besseren Ansatz brauche, da diese Art der Filterung sehr naiv ist (zum Beispiel - die Suche nach "abc" liefert 0 Ergebnisse, dann sollte ich nicht einmal nach "abcX" suchen und so weiter ..)
etaiso
@etaiso richtig (auch wenn Matthews Lösung großartig funktioniert, wenn Sie nicht wirklich alle Übereinstimmungen voreinstellen müssen), habe ich deshalb als zweiten Schritt vorgeschlagen , die Suche zu verfeinern, anstatt jedes Mal eine vollständige Suche durchzuführen.
Adriano Repetti
5
@etaiso Nun, die Suchzeit ist vernachlässigbar, wie ich sagte. Ich habe es mit 120.000 Saiten versucht und die Suche nach einer sehr langen Saite, die keine Übereinstimmungen ergab, und einer sehr kurzen Zeichenfolge, die viele Übereinstimmungen ergab, dauerte beide weniger als 1/50 Sekunde.
Matthew Watson
3
Trägt textBox_search.Texteine messbare Menge zur Zeit bei? Wenn Sie die TextEigenschaft für jede der 120.000 Zeichenfolgen einmal in einem Textfeld abrufen, werden wahrscheinlich 120.000 Nachrichten an das Bearbeitungssteuerungsfenster gesendet.
Gabe
@ Gabe Ja, das tut es. Siehe meine Antwort für Details.
Andris
28

Verwenden Sie den Suffixbaum als Index. Oder erstellen Sie einfach ein sortiertes Wörterbuch, das jedes Suffix jedes Namens mit der Liste der entsprechenden Namen verknüpft.

Zur Eingabe:

Abraham
Barbara
Abram

Die Struktur würde aussehen wie:

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

Suchalgorithmus

Nehmen Sie die Benutzereingabe "BH" an.

  1. Halbieren Sie das Wörterbuch bei Benutzereingaben, um die Benutzereingaben oder die Position zu finden, an die sie gehen könnten. Auf diese Weise finden wir "barbara" - letzte Taste niedriger als "BH". Es heißt Untergrenze für "BH". Die Suche dauert logarithmisch.
  2. Iterieren Sie ab dem gefundenen Schlüssel, bis die Benutzereingabe nicht mehr übereinstimmt. Dies würde "bram" -> Abram und "braham" -> Abraham geben.
  3. Verketten Sie das Iterationsergebnis (Abram, Abraham) und geben Sie es aus.

Solche Bäume sind für die schnelle Suche nach Teilzeichenfolgen ausgelegt. Die Leistung liegt nahe bei O (log n). Ich glaube, dieser Ansatz wird schnell genug funktionieren, um direkt vom GUI-Thread verwendet zu werden. Darüber hinaus funktioniert es aufgrund des fehlenden Synchronisationsaufwands schneller als die Thread-Lösung.

Basilevs
quelle
Soweit ich weiß, sind Suffix-Arrays normalerweise die bessere Wahl als Suffix-Bäume. Einfachere Implementierung und geringere Speichernutzung.
CodesInChaos
Ich schlage SortedList vor, das sehr einfach zu erstellen und zu warten ist, und zwar auf Kosten des Speicheraufwands, der durch die Bereitstellung von Listenkapazitäten minimiert werden kann.
Basilevs
Es scheint auch, dass Arrays (und Original-ST) für die Verarbeitung großer Texte ausgelegt sind, während wir hier eine große Anzahl kurzer Blöcke haben, was eine andere Aufgabe ist.
Basilevs
+1 für den guten Ansatz, aber ich würde eine Hash-Karte oder einen tatsächlichen Suchbaum verwenden, anstatt eine Liste manuell zu durchsuchen.
OrangeDog
Gibt es einen Vorteil der Verwendung eines Suffixbaums anstelle eines Präfixbaums?
Jnovacho
15

Sie benötigen entweder eine Textsuchmaschine (wie Lucene.Net ) oder eine Datenbank (Sie können eine eingebettete wie SQL CE , SQLite usw. in Betracht ziehen ). Mit anderen Worten, Sie benötigen eine indizierte Suche. Die Hash-basierte Suche ist hier nicht anwendbar, da Sie nach Unterzeichenfolgen suchen, während die Hash-basierte Suche gut für die Suche nach genauen Werten geeignet ist.

Andernfalls handelt es sich um eine iterative Suche mit einer Schleife durch die Sammlung.

Dennis
quelle
Die Indizierung ist eine Hash-basierte Suche. Sie fügen einfach alle Unterzeichenfolgen als Schlüssel hinzu und nicht nur den Wert.
OrangeDog
3
@OrangeDog: nicht einverstanden. Die indizierte Suche kann als Hash-basierte Suche mit Indexschlüsseln implementiert werden, ist jedoch nicht erforderlich und keine Hash-basierte Suche nach dem Zeichenfolgenwert.
Dennis
@ Tennis zustimmen. +1, um den Geist -1 abzubrechen.
Benutzer
+1, weil Implementierungen wie eine Textsuchmaschine intelligente (er) Optimierungen haben als string.Contains. Dh. Die Suche nach bain bcaaaabaaführt zu einer (indizierten) Sprungliste. Der erste bwird berücksichtigt, stimmt jedoch nicht überein, da der nächste a ist c, sodass zum nächsten übergegangen wird b.
Caramiriel
12

Es kann auch nützlich sein, ein Ereignis vom Typ "Entprellen" zu haben. Dies unterscheidet sich von der Drosselung darin, dass eine Zeitspanne (z. B. 200 ms) gewartet wird, bis die Änderungen abgeschlossen sind, bevor das Ereignis ausgelöst wird.

Siehe Debounce und Gas: eine visuelle Erklärung für weitere Informationen über Entprellung. Ich schätze, dass dieser Artikel auf JavaScript anstatt auf C # ausgerichtet ist, aber das Prinzip gilt.

Dies hat den Vorteil, dass nicht gesucht wird, wenn Sie Ihre Abfrage noch eingeben. Es sollte dann aufhören, zwei Suchvorgänge gleichzeitig durchzuführen.

paulslater19
quelle
Eine C # -Implementierung eines Ereignisdrosslers finden Sie in der EventThrotler-Klasse in der Algorithmia-Bibliothek: github.com/SolutionsDesign/Algorithmia/blob/master/…
Frans Bouma
11

Führen Sie die Suche in einem anderen Thread aus und zeigen Sie eine Ladeanimation oder einen Fortschrittsbalken an, während dieser Thread ausgeführt wird.

Sie können auch versuchen, die LINQ- Abfrage zu parallelisieren .

var queryResults = strings.AsParallel().Where(item => item.Contains("1")).ToList();

Hier ist ein Benchmark, der die Leistungsvorteile von AsParallel () demonstriert:

{
    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
quelle
1
Ich weiß, dass es eine Möglichkeit ist. Meine Frage hier ist jedoch, ob und wie ich diesen Prozess verkürzen kann.
Etaiso
1
@etaiso es sollte nicht wirklich ein Problem sein, es sei denn, Sie entwickeln auf einer wirklich Low-End-Hardware, stellen Sie sicher, dass Sie nicht den Debugger
ausführen, STRG
1
Dies ist kein guter Kandidat für PLINQ, da die Methode String.Containsnicht teuer ist. msdn.microsoft.com/en-us/library/dd997399.aspx
Tim Schmelter
1
@ TimSchmelter, wenn wir über Tonnen von Saiten sprechen, ist es!
Animaonline
4
@TimSchmelter Ich habe keine Ahnung, was Sie beweisen möchten. Die Verwendung des von mir bereitgestellten Codes erhöht höchstwahrscheinlich die Leistung des OP. Hier ist ein Benchmark, der zeigt, wie es funktioniert: pastebin.com/ATYa2BGt --- Zeitraum - -
animaonline
11

Aktualisieren:

Ich habe ein Profil erstellt.

(Update 3)

  • Listeninhalt: Zahlen generiert von 0 bis 2.499,999
  • Filtertext: 123 (20.477 Ergebnisse)
  • Core i5-2500, Win7 64-Bit, 8 GB RAM
  • VS2012 + JetBrains dotTrace

Der erste Testlauf für 2.500.000 Datensätze dauerte 20.000 ms.

Der Schuldige Nummer eins ist der Ruf nach textBox_search.Textinnen Contains. Dadurch wird für jedes Element die teure get_WindowTextMethode des Textfelds aufgerufen. Ändern Sie einfach den Code in:

    var text = textBox_search.Text;
    listBox_choices.DataSource = allUsers.Where(item => item.Contains(text)).ToList();

reduzierte die Ausführungszeit auf 1,858 ms .

Update 2:

Die anderen beiden wichtigen Engpässe sind jetzt der Aufruf von string.Contains(ca. 45% der Ausführungszeit) und die Aktualisierung der Listbox-Elemente in set_Datasource(30%).

Wir könnten einen Kompromiss zwischen Geschwindigkeit und Speichernutzung eingehen, indem wir einen Suffixbaum erstellen, wie Basilevs vorgeschlagen hat, die Anzahl der erforderlichen Vergleiche zu reduzieren und einige Verarbeitungszeit von der Suche nach einem Tastendruck bis zum Laden der Namen aus der Datei zu verschieben könnte für den Benutzer vorzuziehen sein.

Um die Leistung beim Laden der Elemente in das Listenfeld zu erhöhen, würde ich vorschlagen, nur die ersten Elemente zu laden und dem Benutzer anzuzeigen, dass weitere Elemente verfügbar sind. Auf diese Weise geben Sie dem Benutzer eine Rückmeldung, dass Ergebnisse verfügbar sind, damit er seine Suche durch Eingabe weiterer Buchstaben verfeinern oder die vollständige Liste per Knopfdruck laden kann.

Verwenden BeginUpdateund EndUpdatekeine Änderung in der Ausführungszeit von set_Datasource.

Wie andere hier bemerkt haben, läuft die LINQ-Abfrage selbst ziemlich schnell. Ich glaube, Ihr Flaschenhals ist die Aktualisierung der Listbox selbst. Sie könnten etwas versuchen wie:

if (textBox_search.Text.Length > 2)
{
    listBox_choices.BeginUpdate(); 
    listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
    listBox_choices.EndUpdate(); 
}

Ich hoffe das hilft.

Andris
quelle
Ich denke nicht, dass dies irgendetwas wie das verbessern wird BeginUpdateund verwendet EndUpdatewerden soll, wenn Elemente einzeln hinzugefügt werden oder wenn sie verwendet werden AddRange().
Etaiso
Dies hängt davon ab, wie die DataSourceEigenschaft implementiert wird. Es könnte einen Versuch wert sein.
Andris
Ihre Profilerstellungsergebnisse unterscheiden sich stark von meinen. Ich konnte 120.000 Zeichenfolgen in 30 ms durchsuchen, aber das Hinzufügen zur Zeichenliste dauerte 4500 ms. Es hört sich so an, als würden Sie der Listbox in weniger als 600 ms 2,5 Millionen Zeichenfolgen hinzufügen. Wie ist das möglich?
Gabe
@Gabe Während der Profilerstellung habe ich eine Eingabe verwendet, bei der der Filtertext einen großen Teil der ursprünglichen Liste entfernt hat. Wenn ich eine Eingabe verwende, bei der der Filtertext nichts aus der Liste entfernt, erhalte ich ähnliche Ergebnisse wie bei Ihnen. Ich werde meine Antwort aktualisieren, um zu klären, was ich gemessen habe.
Andris
9

Angenommen, Sie stimmen nur mit Präfixen überein, wird die gesuchte Datenstruktur als Trie bezeichnet , auch als "Präfixbaum" bezeichnet. Die IEnumerable.WhereMethode, die Sie jetzt verwenden, muss bei jedem Zugriff alle Elemente in Ihrem Wörterbuch durchlaufen.

Dieser Thread zeigt, wie Sie einen Versuch in C # erstellen.

Groo
quelle
1
Angenommen, er filtert seine Datensätze mit einem Präfix.
Tarec
1
Beachten Sie, dass er die String.Contains () -Methode anstelle von String.StartsWith () verwendet, sodass es möglicherweise nicht genau das ist, wonach wir suchen. Trotzdem - Ihre Idee ist zweifellos besser als die normale Filterung mit der Erweiterung StartsWith () im Präfix-Szenario.
Tarec
Wenn er damit anfängt, kann der Trie mit dem Hintergrundarbeiter-Ansatz kombiniert werden, um die Leistung zu verbessern
Lyndon White,
8

Das WinForms ListBox-Steuerelement ist hier wirklich Ihr Feind. Das Laden der Datensätze wird langsam sein und die ScrollBar wird Sie kämpfen, um alle 120.000 Datensätze anzuzeigen.

Versuchen Sie, eine altmodische DataGridView-Datenquelle für eine DataTable mit einer einzelnen Spalte [Benutzername] zu verwenden, um Ihre Daten zu speichern:

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

Verwenden Sie dann eine DataView im TextChanged-Ereignis Ihrer TextBox, um die Daten zu filtern:

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
quelle
2
+1 Während alle anderen versuchten, die Suche zu optimieren, die nur 30 ms dauert, sind Sie die einzige Person, die erkannt hat, dass das Problem tatsächlich darin besteht, das Listenfeld auszufüllen.
Gabe
7

Zuerst würde ich ändern , wie ListControlIhre Datenquelle sieht, die Sie konvertieren Ergebnis IEnumerable<string>zu List<string>. Insbesondere wenn Sie nur wenige Zeichen eingegeben haben, kann dies ineffizient (und nicht erforderlich) sein. Erstellen Sie keine umfangreichen Kopien Ihrer Daten .

  • Ich würde das .Where()Ergebnis in eine Sammlung einbinden , die nur das implementiert, was von IList(Suche) benötigt wird. Auf diese Weise können Sie für jedes eingegebene Zeichen eine neue große Liste erstellen.
  • Als Alternative würde ich LINQ vermeiden und etwas Spezifischeres (und Optimiertes) schreiben. Behalten Sie Ihre Liste im Speicher und erstellen Sie ein Array übereinstimmender Indizes. Verwenden Sie das Array erneut, damit Sie es nicht bei jeder Suche neu zuweisen müssen.

Der zweite Schritt besteht darin, nicht in der großen Liste zu suchen, wenn eine kleine ausreicht. Wenn der Benutzer "ab" eingibt und "c" hinzufügt, müssen Sie nicht in der großen Liste recherchieren. Die Suche in der gefilterten Liste ist ausreichend (und schneller). Suche jedes Mal verfeinern ist möglich. Führen Sie nicht jedes Mal eine vollständige Suche durch.

Der dritte Schritt kann schwieriger sein: Halten Sie die Daten so organisiert, dass sie schnell durchsucht werden können . Jetzt müssen Sie die Struktur ändern, in der Sie Ihre Daten speichern. Stellen Sie sich einen Baum wie diesen vor:

ABC
 Bessere Decke hinzufügen
 Über der Knochenkontur

Dies kann einfach mit einem Array implementiert werden (wenn Sie mit ANSI-Namen arbeiten, wäre sonst ein Wörterbuch besser). Erstellen Sie die Liste wie folgt (zur Veranschaulichung entspricht sie dem Anfang der Zeichenfolge):

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

Die Suche wird dann mit dem ersten Zeichen durchgeführt:

char letter = textBox_search.Text[0];
if (dictionary.Contains(letter))
{
    listBox_choices.DataSource =
        new MyListWrapper(dictionary[letter].Where(x => x.Contains(textBox_search.Text)));
}

Bitte beachten Sie, dass ich MyListWrapper()wie im ersten Schritt vorgeschlagen verwendet habe (aber ich habe den zweiten Vorschlag der Kürze halber weggelassen. Wenn Sie die richtige Größe für den Wörterbuchschlüssel wählen, können Sie jede Liste kurz und schnell halten, um - vielleicht - etwas anderes zu vermeiden). Beachten Sie außerdem, dass Sie möglicherweise versuchen, die ersten beiden Zeichen für Ihr Wörterbuch zu verwenden (mehr Listen und kürzere). Wenn Sie dies erweitern, haben Sie einen Baum (aber ich glaube nicht, dass Sie so viele Gegenstände haben).

Es gibt viele verschiedene Algorithmen für die Zeichenfolgensuche (mit verwandten Datenstrukturen), um nur einige zu nennen:

  • Suche nach endlichen Zustandsautomaten : Bei diesem Ansatz vermeiden wir das Zurückverfolgen, indem wir einen deterministischen endlichen Automaten (DFA) konstruieren, der gespeicherte Suchzeichenfolgen erkennt. Diese sind teuer in der Konstruktion - sie werden normalerweise mit der Powerset-Konstruktion erstellt -, aber sehr schnell zu verwenden.
  • Stubs : Knuth-Morris-Pratt berechnet einen DFA, der Eingaben mit der zu suchenden Zeichenfolge als Suffix erkennt. Boyer-Moore beginnt am Ende der Nadel mit der Suche, sodass bei jedem Schritt normalerweise eine ganze Nadellänge vorausgesprungen werden kann. Baeza-Yates verfolgt, ob die vorherigen j Zeichen ein Präfix der Suchzeichenfolge waren, und ist daher an die Suche nach Fuzzy-Zeichenfolgen anpassbar. Der Bitap-Algorithmus ist eine Anwendung des Baeza-Yates-Ansatzes.
  • Indexmethoden : Schnellere Suchalgorithmen basieren auf der Vorverarbeitung des Textes. Nach dem Erstellen eines Teilzeichenfolgenindex, beispielsweise eines Suffixbaums oder eines Suffixarrays, können die Vorkommen eines Musters schnell gefunden werden.
  • Andere Varianten : Einige Suchmethoden, beispielsweise die Trigrammsuche, sollen eher eine "Nähe" zwischen der Suchzeichenfolge und dem Text als eine "Übereinstimmung / Nichtübereinstimmung" finden. Diese werden manchmal als "Fuzzy" -Suchen bezeichnet.

Einige Worte zur parallelen Suche. Es ist möglich, aber es ist selten trivial, da der Overhead, um es parallel zu machen, leicht viel höher sein kann als die Suche selbst. Ich würde die Suche nicht parallel durchführen (Partitionierung und Synchronisation werden bald zu umfangreich und möglicherweise komplex), aber ich würde die Suche in einen separaten Thread verschieben . Wenn der Haupt-Thread nicht ausgelastet ist, spüren Ihre Benutzer während der Eingabe keine Verzögerung (sie bemerken nicht, ob die Liste nach 200 ms angezeigt wird, fühlen sich jedoch unwohl, wenn sie 50 ms nach der Eingabe warten müssen). . Natürlich muss die Suche selbst schnell genug sein. In diesem Fall verwenden Sie keine Threads, um die Suche zu beschleunigen, sondern um Ihre Benutzeroberfläche ansprechbar zu halten . Bitte beachten Sie, dass ein separater Thread Ihre Anfrage nicht stelltschneller , die Benutzeroberfläche bleibt nicht hängen, aber wenn Ihre Abfrage langsam war, ist sie in einem separaten Thread immer noch langsam (außerdem müssen Sie auch mehrere sequenzielle Anforderungen verarbeiten).

Adriano Repetti
quelle
1
Wie einige bereits betont haben, möchte OP die Ergebnisse nicht nur auf Präfixe beschränken (dh er verwendet Contains, nicht StartsWith). Nebenbei bemerkt ist es normalerweise besser, die generische ContainsKeyMethode bei der Suche nach einem Schlüssel zu verwenden, um das Boxen zu vermeiden, und noch besser TryGetValue, um zwei Suchvorgänge zu vermeiden.
Groo
2
@Groo du hast recht, wie gesagt es ist nur zu illustrationszwecken. Der Sinn dieses Codes ist keine funktionierende Lösung, sondern ein Hinweis: Wenn Sie alles andere ausprobiert haben - Kopien vermeiden, Suche verfeinern, in einen anderen Thread verschieben - und es nicht ausreicht, müssen Sie die von Ihnen verwendete Datenstruktur ändern . Beispiel ist der Beginn eines Strings, um einfach zu bleiben.
Adriano Repetti
@Adriano danke für die klare und detaillierte Antwort! Ich stimme den meisten von Ihnen erwähnten Dingen zu, aber wie Groo sagte, ist der letzte Teil der Organisation der Daten in meinem Fall nicht anwendbar. Aber ich denke, vielleicht ein ähnliches Wörterbuch mit Schlüsseln wie der enthaltene Buchstabe zu halten (obwohl es immer noch Duplikate geben wird)
etaiso
Nach einer kurzen Überprüfung und Berechnung ist die Idee des "enthaltenen Buchstabens" nicht nur für ein Zeichen gut (und wenn wir Kombinationen von zwei oder mehr
wählen, erhalten
@etaiso Ja, Sie können eine Liste mit zwei Buchstaben führen (um Unterlisten schnell zu reduzieren), aber ein echter Baum funktioniert möglicherweise besser (jeder Buchstabe ist mit seinen Nachfolgern verknüpft, unabhängig davon, wo er sich in der Zeichenfolge befindet, also für "HOME", das Sie haben "H-> O", "O-> M" und "M-> E". Wenn Sie nach "om" suchen, werden Sie es schnell finden. Das Problem ist, dass es ziemlich komplizierter wird und möglicherweise zu viel ist für Sie Szenario (IMO).
Adriano Repetti
4

Sie können versuchen, PLINQ (Parallel LINQ) zu verwenden. Obwohl dies keinen Geschwindigkeitsschub garantiert, müssen Sie dies durch Ausprobieren herausfinden.

D. Gierveld
quelle
4

Ich bezweifle, dass Sie es schneller schaffen werden, aber auf jeden Fall sollten Sie:

a) Verwenden Sie die AsParallel LINQ- Erweiterungsmethode

a) Verwenden Sie einen Timer, um die Filterung zu verzögern

b) Setzen Sie eine Filtermethode auf einen anderen Thread

Behalte string previousTextBoxValueirgendwo eine Art . Erstellen Sie einen Timer mit einer Verzögerung von 1000 ms, der die Suche bei einem Häkchen auslöst, wenn er previousTextBoxValueIhrem textbox.TextWert entspricht. Wenn nicht, weisen Sie previousTextBoxValueden aktuellen Wert neu zu und setzen Sie den Timer zurück. Stellen Sie den Timer-Start auf das Ereignis "Textfeld geändert" ein, damit Ihre Anwendung reibungsloser wird. Das Filtern von 120.000 Datensätzen in 1-3 Sekunden ist in Ordnung, aber Ihre Benutzeroberfläche muss weiterhin reagieren.

Tarec
quelle
1
Ich bin nicht damit einverstanden, es parallel zu machen, aber ich stimme den beiden anderen Punkten absolut zu. Es kann sogar ausreichen, um die Anforderungen der Benutzeroberfläche zu erfüllen.
Adriano Repetti
Ich habe vergessen, das zu erwähnen, aber ich verwende .NET 3.5, daher ist AsParallel keine Option.
Etaiso
3

Sie können auch versuchen, die Funktion BindingSource.Filter zu verwenden. Ich habe es verwendet und es funktioniert wie ein Zauber, um aus einer Reihe von Datensätzen zu filtern, jedes Mal, wenn diese Eigenschaft mit dem zu durchsuchenden Text aktualisiert wird. Eine andere Option wäre die Verwendung von AutoCompleteSource für das TextBox-Steuerelement.

Ich hoffe es hilft!

NeverHopeless
quelle
2

Ich würde versuchen, die Sammlung zu sortieren, nur nach dem Startteil zu suchen und die Suche um eine bestimmte Zahl zu begrenzen.

so weiter Ininialisierung

allUsers.Sort();

und suchen

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

Vielleicht können Sie einen Cache hinzufügen.

hardsky
quelle
1
Er arbeitet nicht mit dem Beginn eines Strings (deshalb verwendet er String.Contains ()). Mit Contains () ändert eine sortierte Liste die Leistung nicht.
Adriano Repetti
Ja, mit 'Enthält' ist es nutzlos. Ich mag Vorschläge mit dem Sufix-Baum stackoverflow.com/a/21383731/994849 Es gibt viele interessante Antworten im Thread, aber es hängt davon ab, wie viel Zeit er für diese Aufgabe aufwenden kann.
Hardsky
1

Verwenden Sie Parallel LINQ. PLINQist eine parallele Implementierung von LINQ to Objects. PLINQ implementiert den vollständigen Satz von LINQ-Standardabfrageoperatoren als Erweiterungsmethoden für den Namespace T: System.Linq und verfügt über zusätzliche Operatoren für parallele Operationen. PLINQ kombiniert die Einfachheit und Lesbarkeit der LINQ-Syntax mit der Leistung der parallelen Programmierung. Genau wie Code, der auf die Task Parallel Library abzielt, skalieren PLINQ-Abfragen im Grad der Parallelität basierend auf den Funktionen des Host-Computers.

Einführung in PLINQ

Grundlegendes zur Beschleunigung in PLINQ

Sie können auch Lucene.Net verwenden

Lucene.Net ist ein Port der Lucene-Suchmaschinenbibliothek, der in C # geschrieben wurde und sich an .NET-Laufzeitbenutzer richtet. Die Lucene-Suchbibliothek basiert auf einem invertierten Index. Lucene.Net hat drei Hauptziele:


quelle
1

Nach dem, was ich gesehen habe, stimme ich der Tatsache zu, die Liste zu sortieren.

Das Sortieren, wenn die Liste erstellt wird, ist jedoch sehr langsam. Wenn Sie beim Erstellen sortieren, haben Sie eine bessere Ausführungszeit.

Andernfalls verwenden Sie eine Hashmap, wenn Sie die Liste nicht anzeigen oder die Reihenfolge beibehalten müssen.

Die Hashmap hasht Ihre Zeichenfolge und sucht nach dem genauen Versatz. Es sollte schneller sein, denke ich.

Dada
quelle
Hashmap mit welchem ​​Schlüssel? Ich möchte in der Lage sein, Schlüsselwörter zu finden, die in den Zeichenfolgen enthalten sind.
Etaiso
Für den Schlüssel können Sie die Nummer in die Liste aufnehmen. Wenn Sie mehr Komplikation wünschen, können Sie die Nummer plus den Namen hinzufügen. Sie haben die Wahl.
Dada
für den Rest habe ich entweder nicht alles gelesen, es gab auch eine schlechte Erklärung (wahrscheinlich beides;)) [quote] habe eine Textdatei von ungefähr 120.000 Benutzern (Strings), die ich in einer Sammlung speichern und später ausführen möchte Suche in dieser Sammlung. [/ quote] Ich dachte, es wäre nur eine Zeichenfolgensuche.
Dada
1

Versuchen Sie, die BinarySearch-Methode zu verwenden. Sie sollte schneller funktionieren als die Contains-Methode.

Enthält ein O (n) BinarySearch ist ein O (lg (n))

Ich denke, dass sortierte Sammlungen bei der Suche schneller und beim Hinzufügen neuer Elemente langsamer funktionieren sollten, aber wie ich verstanden habe, haben Sie nur Probleme mit der Suchleistung.

user2917540
quelle