Hallo,
ich benötige wieder einmal eine gute Idee.
Ich habe eine sortierte Stringliste der Form (Ausschnitt)

die im Moment 16000 Einträge enthält (in Zukunft weiter wachsend). Die Begriffe sind von den Zahlangaben mit einem Tabulator getrennt.
Mein Problem ist, dass ich möglichst schnell einen Eintrag finden möchte. Bisher durchsuche ich die ganze Stringliste nach einem Begriff s mit

Der gefundene Eintrag wird anschließend in Begriff und Zahl zerlegt. Das funktioniert an sich, ist aber gerade für Strings mit Anfangsbuchstaben am Ende des Alphabets ziemlich langsam.

Die Listenfunktion indexof(s) bringt leider nichts, da dort nur nach dem ganzen String gesucht wird.
Problematisch ist außerdem, dass auch Einträge mit Umlauten als Anfangsbuchstaben auftreten und die Liste bei verschiedenen Windows-Versionen (XP, Vista, 7) unterschiedlich sortiert wird; jedenfalls auf meinen Testrechnern. Ich verstehe es zwar nicht, aber es ist so.
Ein Zerlegen der Liste in zwei Listen, zum einen in die Begriffe, zum anderen in die Zahlen, ist mir gerade wegen der Sortierung bisher nicht geglückt. Außerdem muss der gesuchte Begriff genau mit dem Listeneintrag übereinstimmen.
Suche ich z.B. in meinem Beispiel oben den Begriff "Menge", so darf nicht "abgeschlossene Menge" als Lösung gefunden werden, sondern der wesentlich später folgende Eintrag "Menge".

Sieht jemand von Euch eine Möglichkeit, wie ich die Suche beschleunigen kann. Danke.

Beste Grüße
Mathematiker

Hallo,

eine Stringlist hat die Eigenschaft .sorted, die man auf true setzen kann.
docs.embarcadero.com...ringList_Sorted.html
Dann ist .find anwendbar und schnell, da es binäre Suche anwendet.
docs.embarcadero.com...ses_TStringList.html
oder hier:
www.delphibasics.co....asp?Name=TStringList
Für Deinen speziellen Fall müsstest Du ein CostumSort erstellen.
www.entwickler-ecke....highlight=customsort

Gruß Horst

Wenn ich das richtig verstanden habe, soll als Suchbegriff auch ein Teilstring (der aber am Anfang stehen muss) zulässig sein. AFAIK vergleicht Find aber den gesamten String. Somit wird wohl nichts anderes übrig bleiben, als eine eigene binäre Suche zu implementieren, die dann mit AnsiStartsText/AnsiStartsStr den jeweiligen Stringanfang vergleicht.

Hallo,
Danke für beide Antworten.
Tstringlist.find ist eine schöne, da schnelle Sache. Leider hilft es mir nicht wirklich, da auch hier wieder der gesuchte String absolut identisch sein muss. Und durch die vor der Suche unbekannten Zahlen wird leider nichts gefunden.

Die Idee mit AnsiStartsText/AnsiStartsStr würde wahrscheinlich etwas beschleunigen. Nur leider kennt mein Delphi 5 in der Strutils diese Anweisungen noch nicht.
Die binäre Suche habe ich schon selbst versucht umzusetzen. Die "doofen" Umlaute haben bisher stets gestört. Ich werde weiter experimentieren.

Beste Grüße
Mathematiker

Ich will keine Rechte verletzen, deshalb poste ich hier keinen Original-Code. Als Tipp sei aber gesagt, dass AnsiStartsText intern auf die API-Funktion CompareString zurückgreift.

Hallo,
Ich habe jetzt eine zweite zusätzliche Liste erstellt, die nur die Begriffe enthält. Das verzögert zwar etwas den Programmstart, aber die Suche wird deutlich schneller.

Verrückt ist nur, dass beim Kopieren der Begriffe aus einer sortierten liste1 in eine sortierte liste2 sich die Reihenfolge der Begriffe durch das fehlende Tabulatorzeichen ändert!
Daraufhin habe ich bei der 2.Liste sorted=false gelassen. Tstringlist.find funktioniert trotzdem, bis jetzt!
Das ist alles etwas merkwürdig.

Beste Grüße
Mathematiker

Die Frage ist, ob deine Daten überhaupt so sinnvoll gespeichert sind. Für mich klingt dein Problem total nach einer Hashtabelle (suchen geht dann sozusagen "sofort"). Eine Hashtable braucht beim Vergrößern allerdings O(n) (also solange wie deine Suche, alle durchzuprobieren). Das kommt aber nicht so oft vor, und ich denke da kann man auch noch was machen, kommt auf dein Lastprofil an.

Interessant wären folgende Punkte:
-wie oft musst du suchen
-suchst du immer nach dem String, oder auch nach der Zahl?
-welche Werte musst du auslesen können?
-wie oft, wieviel musst du denn Einfügen
(binäre Suche und schnelles Einfügen widerspricht sich irgendwie, eine Hashtabelle kann aber beides...solange noch Platz ist )

Bzgl hashtable kannst du mal hier gucken:
www.entwickler-ecke....ewtopic.php?t=102753 (XVHashing.pas).
Die sollte mittlerweile fehlerfrei sein, hab die ich schon ziemlich oft verwendet (mit zum Teil über 1Mio Einträgen). Ich würde dann noch was dazu schreiben, wenns in die richtige Richtung geht

PS: Die Hashtabelle aufbauen dauert natürlich auch etwas, wenn du also die sortierte Liste irgendwoher bekommst und nur einmal suchen willst, macht es keinen Sinn, eine Hashtabelle zu benutzen.

Wie wäre es mit THashedStringList, die bei Delphi dabei ist? (Ich weiß nicht seit welcher Version, aber jedenfalls schon länger.)

Da bei dir Delphi 5 steht, wird das wohl nicht in Frage kommen, aber in einigermaßen aktuellen Delphiversionen (2009+) gibt es auch noch TDictionary, das noch einmal sehr viel schneller ist.

Wenn Du hinten immer nur eine Zahl hast würde ich die garnicht mit in den String schreiben sondern in Object. Also entweder sl.AddObject(String, Zahl) verwenden, oder sl.Objects[sl.Add('bla')]. Wobei sl die StringListe ist. Dann kannst Du einfach mit einer sortierten Liste (sl.Sorted=true) arbeiten und hast das Problem mit dem Tabulatorzeichen nicht. Denn das brauchst Du ja nicht mehr. Um den Speed beim reinfüllen zu erhöhen kann man die zu erwartende Größe (Anzahl der Datensätze) der Liste vorher mit Capacity festlegen.
Allerdings würde ich immer einer MemTable den Vorzug geben, was aber bei deiner alten Delphi Version ein bisschen eng wird, da kaum noch unterstüzt. Selbst mein D7 fällt immer mehr raus *heul*.

Hallo Xion,

Xion hat folgendes geschrieben :

-wie oft musst du suchen -suchst du immer nach dem String, oder auch nach der Zahl? -welche Werte musst du auslesen können? -wie oft, wieviel musst du denn Einfügen

Die Liste enthält Schlagwörter eines Lexikons. Die angegebenen Zahlen sind die Seitenzahlen mit dem entsprechenden Begriff. Deshalb kann ich schlecht einschätzen, wie oft zu suchen ist. Je nach Nutzer werden die Links zu den Seiten mehr oder weniger genutzt.
Praktisch muss ich nur nach den Begriffen suchen. Die Seitenzahlen werden ohne Suche direkt aufgerufen.

Xion hat folgendes geschrieben :

Bzgl hashtable kannst du mal hier gucken: www.entwickler-ecke....ewtopic.php?t=102753 (XVHashing.pas).

Danke. Das finde ich sehr interessant und werde es mir heute noch genau ansehen.

Hallo Jaenicke,

jaenicke hat folgendes geschrieben :

Wie wäre es mit THashedStringList, die bei Delphi dabei ist?

Bei Delphi 5 gibt es THashedStringList noch nicht.
Irgendwann muss ich wohl auf ein modernes Delphi umsteigen. Aber ich liebe mein Delphi 5 geradezu.

Hallo Sinspin,

Sinspin hat folgendes geschrieben :

Wenn Du hinten immer nur eine Zahl hast würde ich die garnicht mit in den String schreiben sondern in Object. Also entweder sl.AddObject(String, Zahl) verwenden, oder sl.Objects[sl.Add('bla')]. Wobei sl die StringListe ist.

Danke. Auch das klingt sehr gut. Mit dieser Art von Objekten habe ich noch gar keine Erfahrung. Muss ich mir unbedingt ansehen, denn das erscheint mir am schnellsten umsetzbar.

Beste Grüße
Mathematiker

Mathematiker hat folgendes geschrieben :

Hallo Sinspin, Sinspin hat folgendes geschrieben : Wenn Du hinten immer nur eine Zahl hast würde ich die garnicht mit in den String schreiben sondern in Object. Also entweder sl.AddObject(String, Zahl) verwenden, oder sl.Objects[sl.Add('bla')]. Wobei sl die StringListe ist. Danke. Auch das klingt sehr gut. Mit dieser Art von Objekten habe ich noch gar keine Erfahrung. Muss ich mir unbedingt ansehen, denn das erscheint mir am schnellsten umsetzbar.

Nee, ich meine nichtmal das Du Objekte benutzt. Sondern dass du einfach nur den Pointer auf das Objekt (was Du ja nicht anlegst) misbrauchst. Ein Pointer oder Zeiger auf ein Objekt ist ja auch nur eine Zahl, Typ Integer(Cardinal) in der Regel. Die Zahl wird halt sonst nur als Adresse im Speicher verstanden, in deinem Fall nimmst Du die Zahl direkt.

Mathematiker hat folgendes geschrieben :

die im Moment 16000 Einträge enthält (in Zukunft weiter wachsend).

Da könnte man schon langsam über den Einsatz einer Datenbank nachdenken.

Also wenn der Nutzer suchen soll, dann würde ich auch eine Datenbank bevorzugen. Im Gegensatz zur Hashtabelle kommt die Datenbank auch mit Teiltexten klar (wenn man z.B "Bauernmultiplikation" sucht). Mit SQLite z.B. brauchst du auch keine Treiber und andren Kram zu installieren. Die Datenbank ist dann nur eine Datei und eine .dll.
Die Hashtabelle kommt mir zudem nicht mehr so geeignet vor, weil du sagst dass nur der Nutzer sucht (ich dachte eher ein Algorithmus sucht sehr oft). Die Hashtabelle muss ja erstmal aufgebaut werden, also alle Einträge müssen abgelegt werden. Bei einer Datenbank musst du das nur einmal machen (nicht bei jedem Programmstart). Ist auch viel speicherfreundlicher

evtl. Problem: Wenn sich das Inhaltsverzeichnis ändert (von außen), dann müsstest du die Datenbank neu aufbauen. Wenn du selbst das Inhaltsverzeichnis änderst, wäre es natürlich kein Problem. Kommt ganz drauf an, wo das Inhaltsverzeichnis her kommt und wer es verändert.

Wenn das ganze Zeugs auch irgendwo gespeichert werden soll, erscheint auch mir eine DB sinnvoll. Trotzdem habe ich mir mal den Spaß gemacht und unter Delphi 5 ein kleines Testprogrämmchen mit einer Binärsuche geschrieben. Wirklich langsam kommt mir persönlich das nicht vor.

Hallo,
gegenwärtig habe ich Folgendes schon probiert:

1. meine Anfangslösung ... zu langsam
2. eine zweite Liste ... einfach und schnell
3. Sinspins Hinweis auf addobject ... elegant und sehr schnell; vor allem entfällt das anschließende Zerlegen des Eintrags in Begriff und Seitenzahl

Xions Vorschlag mit der Hashtabelle werde ich probieren. Dazu muss ich das aber erst einmal besser verstehen.
Die Idee mit der Datenbank wird wohl effektiv sein, da nur ich die Liste verändere. Das werde ich auf jeden Fall versuchen.
Aber am reizvollsten und wahrscheinlich sehr schnell (muss ich noch ausführlich testen) ist die binäre Suche von WasWeißDennIch. Damit muss ich nicht unbedingt auf eine Datenbank zugreifen. Die mag ich nämlich nicht. Erklären kann ich die Abneigung allerdings nicht.

Besten Dank an WasWeißDennIch für den Beispiel-Quelltext.
Vielen Dank für die vielen Hinweise an alle.

Beste Grüße
Mathematiker

Sinspin hat folgendes geschrieben :

Nee, ich meine nichtmal das Du Objekte benutzt. Sondern dass du einfach nur den Pointer auf das Objekt (was Du ja nicht anlegst) misbrauchst. Ein Pointer oder Zeiger auf ein Objekt ist ja auch nur eine Zahl, Typ Integer(Cardinal) in der Regel. Die Zahl wird halt sonst nur als Adresse im Speicher verstanden, in deinem Fall nimmst Du die Zahl direkt.

Wobei man dabei dann bei Umstellung auf 64-Bit irgendwann mal heftige und schwer zu findende Probleme bekommen kann. Casten von Zahlen auf Objektpointer usw. ist ganz schlechter Programmierstil...

Wenn, dann kann man kleine Objekte nehmen, die nur einen solchen Wert enthalten, das ist kaum langsamer, kann aber schwerer Probleme verursachen.

Also ich sehe überhaupt keine Verzögerung beim Sortieren, nur irgendwie ist die Suchfunktion nicht immer korrekt. Aber das ist ja bloß ein Test.

Tranx hat folgendes geschrieben :

nur irgendwie ist die Suchfunktion nicht immer korrekt.

Hast Du da gerade mal ein Beispiel?

Hallo,

das dictionary ist eindeutig das schnellste.Du musst nur eine gute Hashfunktion für die Strings finden, um einen guten key zu erzeugen( Strings-> Longint oder word)
Auf Delphi-Praxis gab es die Frage auch mal in Bezug auf 64Bit Zahlen.
www.delphipraxis.net/1159805-post14.html
Mit einer Zeit von 7 Sekunden für das Einfügen von 10e6 Werten kann man wohl leben.16e3 sollten also in 12 ms gespeichert sein.
Der Zugriff über den Key ist dann sozusagen sofort.
Xion's Hashtable sollte also eine wesentliche Beschleunigung bringen.

Gruß Horst

WasWeißDennIch hat folgendes geschrieben :

Tranx hat folgendes geschrieben : nur irgendwie ist die Suchfunktion nicht immer korrekt. Hast Du da gerade mal ein Beispiel?

Ich hatte es mit "drei" im Editfeld versucht, aber es kam nicht immer die erste Zahl mit "drei". Und wenn ich "Drei 6" eingab, kam als Suchwert "drei6" das hat er dann garnicht gefunden.