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 TextBox
Ergebnis 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):
List<string> allUsers;
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?
quelle
HashSet<T>
wird Ihnen hier nicht helfen, weil Sie den Teil der Zeichenfolge suchen .Antworten:
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
_filter
Instanz tatsächlich entsorgen, wenn das übergeordneteForm
Element entsorgt wird. Dies bedeutet , sollten Sie öffnen und bearbeiten Sie IhreForm
‚s -Dispose
Methode (in derYourForm.Designer.cs
Datei) 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.
quelle
_signal.Dispose();
kompilieren kann (Fehler bezüglich der Schutzstufe)._signal.Dispose()
Ist es irgendwo außerhalb derBackgroundWordFilter
Klasse?using
Block verwenden oder anrufenWaitHandle.Close()
.Close()
stattdessen anrufen , was selbst anruft.Dispose()
.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:
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.Text
für jedes Element in auf die Eigenschaft zugreifenallUsers
. 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.Text
500.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.quelle
textBox_search.Text
eine messbare Menge zur Zeit bei? Wenn Sie dieText
Eigenschaft für jede der 120.000 Zeichenfolgen einmal in einem Textfeld abrufen, werden wahrscheinlich 120.000 Nachrichten an das Bearbeitungssteuerungsfenster gesendet.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:
Die Struktur würde aussehen wie:
Suchalgorithmus
Nehmen Sie die Benutzereingabe "BH" an.
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.
quelle
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.
quelle
string.Contains
. Dh. Die Suche nachba
inbcaaaabaa
führt zu einer (indizierten) Sprungliste. Der ersteb
wird berücksichtigt, stimmt jedoch nicht überein, da der nächste a istc
, sodass zum nächsten übergegangen wirdb
.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.
quelle
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); }
quelle
String.Contains
nicht teuer ist. msdn.microsoft.com/en-us/library/dd997399.aspxAktualisieren:
Ich habe ein Profil erstellt.
(Update 3)
Der erste Testlauf für 2.500.000 Datensätze dauerte 20.000 ms.
Der Schuldige Nummer eins ist der Ruf nach
textBox_search.Text
innenContains
. Dadurch wird für jedes Element die teureget_WindowText
Methode 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 inset_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
BeginUpdate
undEndUpdate
keine Änderung in der Ausführungszeit vonset_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.quelle
BeginUpdate
und verwendetEndUpdate
werden soll, wenn Elemente einzeln hinzugefügt werden oder wenn sie verwendet werdenAddRange()
.DataSource
Eigenschaft implementiert wird. Es könnte einen Versuch wert sein.Angenommen, Sie stimmen nur mit Präfixen überein, wird die gesuchte Datenstruktur als Trie bezeichnet , auch als "Präfixbaum" bezeichnet. Die
IEnumerable.Where
Methode, 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.
quelle
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; }
quelle
Zuerst würde ich ändern , wie
ListControl
Ihre Datenquelle sieht, die Sie konvertieren ErgebnisIEnumerable<string>
zuList<string>
. Insbesondere wenn Sie nur wenige Zeichen eingegeben haben, kann dies ineffizient (und nicht erforderlich) sein. Erstellen Sie keine umfangreichen Kopien Ihrer Daten ..Where()
Ergebnis in eine Sammlung einbinden , die nur das implementiert, was vonIList
(Suche) benötigt wird. Auf diese Weise können Sie für jedes eingegebene Zeichen eine neue große Liste erstellen.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:
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:
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).
quelle
Contains
, nichtStartsWith
). Nebenbei bemerkt ist es normalerweise besser, die generischeContainsKey
Methode bei der Suche nach einem Schlüssel zu verwenden, um das Boxen zu vermeiden, und noch besserTryGetValue
, um zwei Suchvorgänge zu vermeiden.Sie können versuchen, PLINQ (Parallel LINQ) zu verwenden. Obwohl dies keinen Geschwindigkeitsschub garantiert, müssen Sie dies durch Ausprobieren herausfinden.
quelle
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 previousTextBoxValue
irgendwo eine Art . Erstellen Sie einen Timer mit einer Verzögerung von 1000 ms, der die Suche bei einem Häkchen auslöst, wenn erpreviousTextBoxValue
Ihremtextbox.Text
Wert entspricht. Wenn nicht, weisen SiepreviousTextBoxValue
den 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.quelle
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!
quelle
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
und suchen
Vielleicht können Sie einen Cache hinzufügen.
quelle
Verwenden Sie Parallel
LINQ
.PLINQ
ist 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
quelle
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.
quelle
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.
quelle