Optimierung eines Suchalgorithmuses

[RattuS]

Hallo,

ihr kennt wahrscheinlich alle diese Sucheingabe, die bei jedem neuen Zeichen nach Treffern sucht, z.B. die Winamp Media Library Suche.
Die gleiche Sucheingabe möchte ich jetzt auch in meinem Programm einbinden, undzwar soll ein DataGridView durchsucht werden. Natürlich war die Umsetzung im ersten Anlauf kein Problem. Allerdings ist der Suchalgorithmus ziemlich naiv und benötigt bei entsprechend großen Listen (5-10k Einträge) extrem lange (5-10 Sekunden). Der Grund ist offensichtlich, da ich die Liste bei jedem neuen Zeichen von Anfang bis Ende neu ablaufe.
Die Winamp Media Library Suche benötigt bei großen Listen allerdings ein vielfaches weniger an Zeit. Wie?

Der Code sieht derzeit etwa so aus:


for i = 0 to Grid.Rows.Count - 1
Grid_Explorer.Rows(i).Visible = True
}

for i = 0 to Grid.Rows.Count - 1
if Grid.Rows[i].Cells[0].Value.ToString.ToLower.Contains(Sucheingabe.Text.ToLower) = false
Grid_Explorer.Rows[i].Visible = false
}


Diese Variante ist natürlich denkbar schlecht, da sie gleich 2 Mal die Liste ablaufen muss. Mir fällt aber leider keine bessere Variante ein. Man könnte die Suche bei nachfolgenden Zeichen vielleicht auf die gefundene Liste bisher eingrenzen, allerdings müsste man dann bei einer Neueingabe trotzdem wieder alle Zeilen zurücksetzen.

Hat jemand einen Vorschlag? :confused:

[Coda]

http://en.wikipedia.org/wiki/Trie bzw http://en.wikipedia.org/wiki/Radix_tree

[Berni]

Im Grunde brauchst du halt eine gute Suchengine wenns schnell sein soll und die Strings müssen eben schon beim Einfügen der Datei in die Bibliothek entsprechend indiziert werden (z.B. in oben genannte Baumstrukturen) damits nachher schnell geht.
Ist zwar vielleicht etwas übertrieben vielleicht aber du könntest auch vielleicht Lucene verwenden ( http://incubator.apache.org/lucene.net/ wäre die .Net-Version) damit du dir das selbstcoden sparen kannst.

[Bietchiebatchie]

Ist zwar vielleicht etwas übertrieben vielleicht aber du könntest auch vielleicht Lucene verwenden ( http://incubator.apache.org/lucene.net/ wäre die .Net-Version) damit du dir das selbstcoden sparen kannst.

Ich bin natürlich prinzipiell für die Nutzung von bestehenden und erfolgreich eingesetzten Komponenten, aber bei 5-10k Einträgen ist Lucene (o.ä) doch ziemlich mit Kanonen auf Spatzen geschossen ;)

Desweiteren glaube ich kaum dass das Durchsuchen von 10k Einträgen 5s dauert - 5ms vielleicht. Der Overhead entsteht wahrscheinlich dadurch, dass du direkt auf dem DataGridView arbeitest - die meisten Rows werden ja auf invisible gesetzt wenn die Schleife darüberläuft und das dauert. (Ich rate hier einfach mal...)

Probier einfach mal folgendes aus:
1. Ein DataGridView mit allen Einträgen.
2. Eine Liste<TInput> und ein Dictionary<TInput, TRowValue> wobei TInput der Teil ist mit dem der Suchbegriff verglichen wird und TRowValue die Daten der dazugehörigen DataRow. (Beides wird natürlich mit den Daten aus 1. gefüttert)
3. Anfangs zeigts du die ganze DataGridView an.
4. Falls ein Suchwort eingegeben wird, erzeugst du eine neue leere DataGridView, dabei
5. iterierst du über die Liste und falls ein Suchtreffer vorliegt füllst du die DataGridView mit den Values des dazugehörigen Dictionary-Eintrags.

Untestet und ohne Gewähr sollte die Laufzeit auch bei 10k Einträgen unbemerkbar sein.

Edit: Mir ist gerade ausgefallen, dass du in keinster Weise die Länge der Texte in den DataGridViewRows erwähnst...
Sollten diese natürlich entsprechend lang sein (> 100 Zeichen) dann ist mein Post natürlich lächerlich - dann doch lieber die Wikipedia-Artikel lesen. Oder falls es wirklich lange Texte sind: siehe Post über mir.

[RattuS]

Desweiteren glaube ich kaum dass das Durchsuchen von 10k Einträgen 5s dauert - 5ms vielleicht. Der Overhead entsteht wahrscheinlich dadurch, dass du direkt auf dem DataGridView arbeitest - die meisten Rows werden ja auf invisible gesetzt wenn die Schleife darüberläuft und das dauert. (Ich rate hier einfach mal...)
Ich denke du liegst hier falsch. Das DataGridView hat in seinen Einträgen nach wie vor ja lediglich Adressoffsets. Im Offset von Visible wird dann halt 1 zu 0. Im Grunde springt der CPU in der Schleife also nur um einen Adresswert und das kostet natürlich keine Zeit.

Vielmehr ist das Problem, und das hattest du ja angesprochen, die Stringmatching-Funktion "contains". Die Strings sind teilweise zwar nur bis zu 30 Zeichen lang, dennoch ist diese Byteoperation definitiv zeitlastig bei einer entsprechenden Menge an Ausführungen.

Probier einfach mal folgendes aus: ...

Eine zusätzliche/n Adressbereich/Liste zu erzeugen ist keine schlechte Idee, denn dann fällt zumindest das "neutralisieren" (eine Schleife) weg, da ich den Adressbereich dann mit dem .Clear ja nullen kann.

Ich teste letztere Variante morgen mal aus und poste das Ergebnis hier. Die Trie-Variante ist für meine Zwecke IMO zu aufwendig.

[Spasstiger]

Du könntest einen Baum erstellen und dabei für jeden Buchstaben im Wort einen Zweig erstellen. Die entsprechenden Einträge stehen dann in den Knoten.
Das Wort "Beispiel" würde vom Startknoten zunächst in den "B"-Zweig laufen, vom neuen Knoten dann in den "e"-Zweig, vom folgenden Knoten in den "i"-Zweig usw. Wenn der Suchbegriff abgearbeitet ist, dann bist du im gewünschten Knoten, der die gewünschten Einträge enthält (oder Verweise darauf).
Und wenn ein Zweig bei der Suche nicht existiert, existiert auch kein Eintrag mit dem Suchbegriff.

Für eine erfolgreiche Suche brauchst du somit nur soviele Suchschritte wie der Suchbegriff Buchstaben hat.
Also 30 Buchstaben = 30 Suchschritte.
Und du sparst dir das contains().

/EDIT: Ok, meine Lösung hat ein kleines Problem, wenn der Suchbegriff nur ein Teil des Wortes ist. Um den Speedvorteil aufrecht zu erhalten, müsste man dann die Einträge sehr redundant speichern.
D.h. man trägt in den Knoten vom Pfad "e"->"i"->"s" alles ein, was die Zeichenkette "eis" enthält. Für große Listen eignet sich diese Lösung also weniger.

[Coda]

Bravo Spasstiger. Du hast soeben einen Trie beschrieben den ich schon im ersten Post verlinkt hatte und als zweiten Link sogar die Lösung für dein Problem :rolleyes:

Es ist alles gesagt. Bitte weitergehen.

[Berni]

/EDIT: Ok, meine Lösung hat ein kleines Problem, wenn der Suchbegriff nur ein Teil des Wortes ist. Um den Speedvorteil aufrecht zu erhalten, müsste man dann die Einträge sehr redundant speichern.
D.h. man trägt in den Knoten vom Pfad "e"->"i"->"s" alles ein, was die Zeichenkette "eis" enthält. Für große Listen eignet sich diese Lösung also weniger.
Man muss einen Baum erstellen, der N-Gramme (normal: Trigramme) enthält, welche dann auf (mehrere) StringIDs verweisen. So wird z.B. "Suche" gespeichert in "Suc", "uch", "che". Das Suchwort wird ebenfalls in Trigramme geteilt. Nun sucht man im Baum nach allen Trigrammen des Suchworts und bildet die Schnittmenge der StringIDs. Das ist natürlich speicheraufwändiger aber dafür bei großen Datenmengen wesentlich schneller...

[pest]

warum nicht einfach Hashing + dynamische Listen?

[Bietchiebatchie]

Ich denke du liegst hier falsch. Das DataGridView hat in seinen Einträgen nach wie vor ja lediglich Adressoffsets. Im Offset von Visible wird dann halt 1 zu 0. Im Grunde springt der CPU in der Schleife also nur um einen Adresswert und das kostet natürlich keine Zeit.
Ich hatte zwar anfangs nur geraten, aber ich war mal so nett und habe das mal schnell getestet:
- eine DataGridView mit 10k Rows füllen: 5-10s
- über alle Rows der View iterieren und visible = false setzen: 1min
- jedesmal eine neue View neu erzeugen, ein Dictionary aus den Einträgen der einzelnen Rows erzeugen, über dieses Dictionary iterieren und die View mit neuen Rows(*)füttern: 100ms

Hmm, relativ eindeutig imo ;)

angenommen die Hitrate liegt bei 5%, also 500 Rows.

[RattuS]

warum nicht einfach Hashing + dynamische Listen?
Weil Teilketten hashen kaum schneller ist. Es geht nicht um Full-Matching, sondern um Partial-Matching.

- über alle Rows der View iterieren und visible = false setzen: 1min
Das Visible = false aller Zeilen dauert bei mir nichtmal 10 Sekunden. :confused:

[Bietchiebatchie]

Keine Ahnung, vielleicht warns auch nur 30s (Laptop).
Ist auch relativ irrelevant.
Die Folgerung bleibt die gleiche: Das Arbeiten auf dem DataGridView verbraucht 99% der Zeit und nicht dein Sortieralgorithmus.

[Gast]

lol Ein DataGridView füllt man auch nicht mit 10k Rows. Bei so vielen Daten implementiert man einen Paging Mechanismus, wo die Daten pro DataGridView Page aus der DB abgerufen werden.

[RattuS]

Ich verwende das DGV nicht im Zusammenhang mit einer Datenbank, sondern als Anzeige von Dateien in einem Verzeichnis. Diese Worst-Case Situation entsteht nur, wenn der Benutzer ein Verzeichnis samt Unterverzeichnisse auslesen möchte, das tief verschachtelt ist. Dieses Szenario ist im Zusammenhang mit dem eigentlichen Programm recht unwahrscheinlich, aber prinzipiell taucht es eben auf.

Problem gelöst. Ich benutze jetzt einfach eine SortedList mit dem String als Key. Das Hashing scheint hier doch Wunder zu bewirken.