Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - Schnelles Suchen in Tstringlist
Mathematiker - So 10.02.13 10:15
Titel: Schnelles Suchen in Tstringlist
Hallo,
ich benötige wieder einmal eine gute Idee.
Ich habe eine sortierte Stringliste der Form (Ausschnitt)
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
| ...
Abendweite 8705
Aberration 8701
abessinische Bauernmultiplikation 102
abgekantete Polyeder 3145
abgekantete Polyeder (2) 3146
abgekantetes 5-Zell 3955
abgekantetes 8-Zell 3958
abgerundete Zahlen 1257
abgeschlossene Kugel 4489
abgeschlossene Menge 61
abgeschlossene Verknüpfung 663
abgeschlossener topologischer Raum 4490
abgeschlossenes Intervall 89
abgeschnittener Sternwürfel 3729
... |
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
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
| gefunden:=false;
j:=0;
repeat
if pos(s,liste[j])=1 then gefunden:=true;
inc(j);
until gefunden or (j>liste.Count-1); |
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
WasWeißDennIch - So 10.02.13 10:50
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.
Mathematiker - So 10.02.13 11:15
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
Mathematiker - So 10.02.13 11:43
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
Xion - So 10.02.13 12:28
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:
http://www.entwickler-ecke.de/viewtopic.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.
jaenicke - So 10.02.13 12:44
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.
Sinspin - So 10.02.13 13:09
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*.
Mathematiker - So 10.02.13 13:29
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.
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. :lol:
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
Gerd Kayser - So 10.02.13 14:19
| 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.
Xion - So 10.02.13 15:52
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.
WasWeißDennIch - So 10.02.13 16:12
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.
Mathematiker - So 10.02.13 16:23
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
jaenicke - So 10.02.13 18:43
| 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.
Tranx - So 10.02.13 19:40
Also ich sehe überhaupt keine Verzögerung beim Sortieren, nur irgendwie ist die Suchfunktion nicht immer korrekt. Aber das ist ja bloß ein Test.
WasWeißDennIch - So 10.02.13 19:52
| Tranx hat folgendes geschrieben : |
| nur irgendwie ist die Suchfunktion nicht immer korrekt. |
Hast Du da gerade mal ein Beispiel?
Horst_H - Mo 11.02.13 14:44
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.
http://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 - Mo 11.02.13 18:37
Das mit "drei" kann ich nicht nachvollziehen, "drei 6" ist einfach erklärt: die Zahl ist nicht Bestandteil des Strings und wird somit auch in der Suche gar nicht einbezogen, sondern wurde lediglich in der Listbox mit dargestellt. Im Nachhinein fällt mir ein, dass ich statt der ListBox wohl besser eine ListView im Stil vsReport mit 2 Spalten genommen hätte, dann wäre die Trennung auch optisch besser erkennbar gewesen. Mea culpa, aber es sollte ja auch nur eine kleine Mini-Demo sein, ich habe ja nicht einmal die Standardbezeichner geändert.
Tranx - Mo 11.02.13 20:41
Ist doch kein Problem. Die Sache hat mich nur interessiert, wegen der Frage, ob das eine langsame Sortierfunktion ist. Alles andere war mir nicht so wichtig. Und ich muss sagen, ich habe keinerlei Verzögerung festgestellt. Mir kam es so vor, als wäre da garnichts sortiert worden. So schnell ging das.
Xion - Di 12.02.13 10:25
| Horst_H hat folgendes geschrieben : |
| Du musst nur eine gute Hashfunktion für die Strings finden, um einen guten key zu erzeugen( Strings-> Longint oder word) |
Das ist ein Argument. Da ich es absolut nicht ausstehen kann, sich auf den Zufall zu verlassen (nach dem Motto: mit einer guten Hashfunktion gibts keine Kollisionen) habe ich mal im Anhang ein kleines Testprogramm geschrieben:
- ich lese aus einer Datei (bezogen von hier:
http://www.minorplanetcenter.net/iau/lists/MPNames.html ) Namen und die Zahlen ein. Ich speichere das in ein Array.
- dann hashe ich die Namen auf eine sehr simple Weise und sorge aber dafür, dass ich auch bei Kollisionen noch meine echten Namen finde. Als Key speichere ich dann den Hash und als Wert den Index in die Datenbasis.
- beim Lesen wieder das selbe. Da gucke ich dann, ob ich auch wirklich den richtigen Wert aus der Hashtable bekommen habe, wenn nicht, dann sondiere ich.
- das Einfügen ist leider nicht so flott, wie ich gehofft hatte. Brauche etwa 1 Sekunde für die 18k Einträge.
- das Suchen ist wie immer bei Hashtables fies schnell: 20ms für 18k mal suchen. Man müsste sich mal überlegen, warum das Einfügen so lange dauert, da dort ja eigentlich auch nur gesucht wird.
- Der Code kann noch nicht Werte aus der Hashtable löschen. Dazu müsste man wieder den Namen hashen, solange sondieren bis man den richtigen Eintrag gefunden hat, dann den entsprechenden Wert löschen.
- die Fehlerausgabe der Hashtable über die Strings ist nicht so hübsch, und außerdem würde ich heute auch die Hashtable automatisch das Vergrößern übernehmen lassen. "Damals" hielt ich das noch für gut so ;)
Mathematiker - Di 12.02.13 10:54
Hallo Xion,
Deine Lösung ist genial.
Ich habe es für meine 16000 Einträge leicht modifiziert und es funktioniert absolut einwandfrei.
Das Einlesen dauert 390 ms, die Suche nach den Einträgen 78 ms und ohne Fehler. Perfekter geht's es kaum.
Besten Dank und ich denke, dass ich es jetzt auch verstanden habe. Wenigstens einigermaßen. :lol:
Beste Grüße
Mathematiker
jaenicke - Di 12.02.13 13:57
Ich habe die Lösung mal 1:1 mit TDictionary und Delphi XE getestet. Mit GetTickCount ist die Zeit, die dann benötigt wird, nicht messbar, es ist etwa 1ms (also mehr als 100 mal schneller), wenn man zusätzlich noch das Einlesen der Datei optimiert, ebenso die Zugriffe, auch diese dauern alle zusammen unter 1ms. Ein entsprechendes Demoprogramm hänge ich mal heute Abend an, denn die meiste Zeit geht soweit ich das sehe für das Einlesen der Datei drauf, weil das nicht gerade optimal passiert.
Horst_H - Di 12.02.13 17:16
Hallo,
schade das
Mathematiker bei Delphi 5 bleiben will ;-)
Aber ich bin auch etwas erstaunt, warum es 390 ms dauern soll, wenn 25 Mio Einträge bei mir in 7 Sekunden eingetragen sind.Dabei ging es um Int64 , aber 8 Byte vergleichen dauert auch bei Strings nicht sehr lang.
Gruß Horst
Mathematiker - Di 12.02.13 18:05
Hallo Horst_H,
| Horst_H hat folgendes geschrieben : |
| Aber ich bin auch etwas erstaunt, warum es 390 ms dauern soll, wenn 25 Mio Einträge bei mir in 7 Sekunden eingetragen sind. |
Nun ja, ich habe nicht nur ein steinaltes Delphi, mein PC gilt bestimmt schon als Museumsstück: 6 Jahre alt mit 1,73 GHZ und 1 GB Hauptspeicher und das bei Vista!
Um ehrlich zu sein, gibt es mehrere Gründe:
Erstens sind mir moderne Delphi-Compiler zu teuer! Meine Versuche mit Lazarus waren eine absolute Pleite.
Zweitens habe ich mich nach 12 Jahren an mein Delphi 5 gewöhnt. Ich liebe es. :D Und wenn es einmal spinnt, dann beruhigte es sich nach einem Neustart immer wieder. Bis jetzt hat es alles gemacht, was ich wollte.
Drittens habe ich beim letzten Umstieg des PCs 14 Tage gebraucht, alle Zusatzkomponenten so einzurichten, dass alles wieder funktioniert. Und ich fürchte bei einem neuen Delphi wird es schlimmer.
Und der wichtigste Grund: Ich arbeite seit Jahren an einem sehr umfangreichen Programm. Der Versuch eines Umstiegs auf XE oder Ähnliches würde wohl eine Katastrophe werden.
2000 habe ich schon einmal alles von Borland Pascal für Windows auf Delphi umgestellt. Ich war damals wochenlang nicht ansprechbar.
"Never change a running system!" ist meine oberste Maxime. :mrgreen:
Dass ich dadurch auf viele neue Möglichkeiten verzichten muss, ist schade. Solange Microsoft mit einem neuen Windows nicht verhindert, dass Delphi 5-Programme laufen, werde ich wohl nicht umstellen.
Das war zwar jetzt alles Off Topic, aber was soll's.
Beste Grüße
Mathematiker
Xion - Di 12.02.13 18:55
Ich hab mich mal etwas umgeguckt. Unter Andrem ist mir aufgefallen, dass Variant garkeine Records aufnehmen kann (womit mein Plan, die Hashtable generisch zu machen, schon versagt hat). Und dass es wohl nicht so schnell sein soll. Es wäre wohl viel cleverer, in der Hashtable Pointer (oder integer) zu benutzen (zumindest in diesem Fall). Pointer find ich zwar normal nicht so schön, weil man sich dann selbst um die Aufbewahrung der Daten kümmern muss (in einem Array z.B) und nicht mal eben ein paar Integer in die Hashtabelle speichern und wieder löschen kann, aber ich denke es wäre wohl in diesem Fall die bessere Wahl. Oder eben gleich nur Integer zulassen, und die als Arrayindex verwenden.
Wieviel das bringt, keine Ahnung. Habe gerade auch nicht die Muße, das weiter zu verfolgen. Es wäre zumindest eine Erklärung, warum das Einfügen so lange dauert.
Horst_H - Di 12.02.13 19:08
Hallo,
ich habe mal alzaimar csDictionary benutz un es ist wesentlich schneller:
Diese Wortliste mit 172823 Worten habe ich genutzt, aber nicht angehängt, eine ältere Version von diesem:
http://scrabble-dictionary-search.googlecode.com/svn-history/r6/trunk/src/main/resources/enable1.txt
Ausgabe
Quelltext
1:
2:
3:
4:
| TotalCOunt : 172823
Einfuegen von 172823 verschiedenen Daten in 00:00:00,187
Finden von 0 falschen Daten in 00:00:00,140
Aufloesen der Hashmap in 00:00:00,047 |
Wenn es bei mir 20 mal schneller ist als bei Mathematiker, trotz der 10-fachen Datenmenge, müßte es bei ihm immer noch erheblich schneller sein, zumal Delphi5 gegen Freepascal wohl noch gewinnt.
Gruß Horst
Mathematiker - Di 12.02.13 19:56
Hallo Horst_H,
| Horst_H hat folgendes geschrieben : |
| Wenn es bei mir 20 mal schneller ist als bei Mathematiker, trotz der 10-fachen Datenmenge, müßte es bei ihm immer noch erheblich schneller sein, zumal Delphi5 gegen Freepascal wohl noch gewinnt. |
Deine Liste enthält nur Begriffe, bei meiner muss der String noch in den Begriff und die Seitenzahl zerlegt werden. Genau das kostet die Zeit. 32000 copy-Befehle brauchen ihre Zeit.
Zuerst dachte ich, dass meine Änderung in Xions Text die Zeit kostet. Ich musste inline entfernen, ja ja, mein Delphi 5. :wink:
Das war aber nicht wirklich hemmend.
Erstaunt bin ich aber, dass bei 16000 Einträgen 80294 Kollisionen gemeldet werden. Irgendetwas mache ich wieder falsch.
Beste Grüße
Mathematiker
Xion - Di 12.02.13 20:24
| Mathematiker hat folgendes geschrieben : |
| Erstaunt bin ich aber, dass bei 16000 Einträgen 80294 Kollisionen gemeldet werden. Irgendetwas mache ich wieder falsch. |
Oha! Das liegt an der einfachen String-hash-funktion, die ich in dem Tesprojekt benutzt habe. Probiere mal was andres. Insbesondere: Breche nicht nach 10 Zeichen ab, wenn du Texte hast, welche bei den ersten 10 Zeichen gleich sind.
Du bist doch "Mathematiker", also denk dir mal was schlaues aus ;) Du musst nur dafür sorgen, dass die verschiedenen Zeichenketten möglichst auf verschiedene Integer verteilt werden.
Horst_H - Di 12.02.13 22:18
Hallo,
An
Mathematiker:
Vielleicht wäre in Deinem speziellen Fall sogar die Seitenzahl ein guter HashWert.
csDictionary nutzt bei einer Kollision eine einfache lineare Liste an der Stelle der Kollision, statt einen neuen Hashwert zu erstellen.
csDictionary nutzt diese Funktion, um einen Hashwert zu berechnen:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
| Function HashFromStr(Const Value: String): Cardinal; Var
i: Integer;
x: Cardinal;
Begin
Result := 0;
For i := 1 To Length(Value) Do Begin
Result := (Result Shl 4) + Ord(Value[i]);
x := Result And $F0000000;
If (x <> 0) Then
Result := Result Xor (x Shr 24);
Result := Result And (Not x);
End;
End; |
Gruß Horst
Mathematiker - Di 12.02.13 23:08
Hallo Horst_H,
mit Deiner Super-Hash-Funktion habe ich jetzt das Eintragen auf 290 ms verkürzt, bei nur 15 Kollisionen. D.h., ziehe ich die Zeit 110 ms für das Lesen des Files und das Aufspalten ab, bin ich jetzt unter 200 ms. Das ist für meinen Rechner richtig schnell.
Die Suche nach allen 16000 Einträgen dauert nun auch nur 15 ms, also superschnell.
Vielen Dank für Deine Hilfe.
Beste Grüße
Mathematiker
Xion - Mi 13.02.13 08:38
| Horst_H hat folgendes geschrieben : |
| Vielleicht wäre in Deinem speziellen Fall sogar die Seitenzahl ein guter HashWert. |
Das ist zwar intuitiv, aber Quatsch. Die Hashtabelle wird ja benutzt, um den String zu suchen und die Seitenzahl
auszugeben. Wenn ich fürs Suchen aber erst die Seitenzahl wissen muss, um den Hash-Wert zu berechnen, um die Hashtabelle zu benutzen, um die Seitenzahl zu einem Begriff zu suchen.... Du verstehst? :mrgreen:
Die Seitenzahl wäre toll, wenn man zu einer Seitenzahl den Begriff sucht ;)
Horst_H - Mi 13.02.13 09:05
Hallo,
für wahr, wie grottig von mir, die Umkehrung ist nicht wirklich hilfreich :-)
Hat hier jemand schon die TStringlist mit Name,Value Werten getestet, ob dort sort auch funktioniert?
Man muss ja als NameValueSeperator nicht unbedingt TAB nehmen, es geht ja auch "=".
Aber wenn
Mathematiker mit seiner Hashtabelle nun gut zufrieden ist, ist ja alles gut.
Gruß Horst
Mathematiker - Mi 13.02.13 09:30
Hallo,
| Horst_H hat folgendes geschrieben : |
| Hat hier jemand schon die TStringlist mit Name,Value Werten getestet, ob dort sort auch funktioniert? |
Habe ich und da gibt es ein richtiges Problem.
Enthält die Sortierliste z.B. die Einträge Menge[Tabulator]345 und Menge (2)[Tabulator]567, dann sortiert die Stringliste in der Reihenfolge
| Zitat: |
Menge (2)[Tabulator]567
Menge[Tabulator]345
|
also verkehrt herum. Fehlt der Tabulator wird richtig
Bisher helfe ich mir mit einem zusätzlichen Leerzeichen
| Zitat: |
Menge [Tabulator]345
Menge (2)[Tabulator]567
|
Warum ein Lerzeichen vor(!) dem Tabulatorzeichen #9 einsortiert wird, verstehe ich nicht.
| Horst_H hat folgendes geschrieben : |
| Aber wenn Mathematiker mit seiner Hashtabelle nun gut zufrieden ist, ist ja alles gut. |
Ich bin sehr zufrieden und danke Euch für Eure große Hilfe.
Aber natürlich kann man ja weiter nach Optimierungen suchen. :mrgreen:
Beste Grüße
Mathematiker
Martok - Mi 13.02.13 11:57
| Mathematiker hat folgendes geschrieben : |
Hallo,
| Horst_H hat folgendes geschrieben : | | Hat hier jemand schon die TStringlist mit Name,Value Werten getestet, ob dort sort auch funktioniert? |
|
THashedStringList: Einfügen "wie normal", der erste Suchvorgang (IndexOfName) baut den Index und kostet deswegen 300ms, jeder weitere ~0.15ms. Gemessen mit PerformanceCounter.
| Mathematiker hat folgendes geschrieben : |
| Aber natürlich kann man ja weiter nach Optimierungen suchen. :mrgreen: |
Hashmap nur aktualisieren, nachdem alles eingefügt ist; AVL-Trees (lohnt sich bei den paar Elementen kaum); binäre Suche auf sortierter Liste, ggf. eine doppelt verkettete Liste, InsertionSort geht dann sehr schön (da kostet das Insert nämlich nix mehr).
Warum hat
Gausi hier eigentlich noch nix geschrieben :gruebel:
Xion - Mi 13.02.13 23:05
| Martok hat folgendes geschrieben : |
| binäre Suche auf sortierter Liste |
Das fasziniert mich. Kannst du mal kurz skizzieren, wie das geht? Typischerweise kann man bei Listen nicht in O(1) auf ein bestimmtes (das mittlere) Objekt zugreifen.
Binäre Suche hat außerdem Komplexität O(logn), also deutlich schlechter als O(1) für die Hashtable.
| Martok hat folgendes geschrieben : |
| AVL-Trees (lohnt sich bei den paar Elementen kaum) |
AVL hat als Baum auch Komplexität O(logn), und ist im Endeffekt dann nur eine balancierte Variante vom binären Suchen (was auch ziemlich balanciert ist :P). Ich denke AVL bringt da keine Vorteile. Die Implementierung ist dafür schön knifflig :mrgreen: .
Ich hätte da noch Patricia Tries ins Rennen zu werfen ;) Bei sehr langen, unterschiedlichen Texten ist das (theoretisch) besser als die Hashfunktion zu berechnen, wenn man davon ausgeht, dass man immer nach Strings sucht, die auch enthalten sind, weil man evtl nur das Anfangsstück lesen muss. Hier hätte man wohl Komplexität O(m) mit m=Länge des zu suchenden Begriffs. Da die Hashfunktion auch O(m) hat, könnte das theoretisch Sinn machen. Praktisch kriegt man da wohl vom Cache paar auf die Finger ;)
Mathematiker - Mi 13.02.13 23:37
Hallo,
ich habe mich nun für Xions-Hashunit mit Horst_Hs Hash-Funktion entschieden und heute einen Testlauf durchgeführt.
Die 9000 Textseiten mit über 8000 Abbildungen werden auf meinem alten Computer in nur 250 Sekunden alle in der Hash-Tabelle gefunden, Text und Bild aus DLLs gelesen und anschließend angezeigt. Das sind 35 Seiten je Sekunde, also superschnell. Bei dieser Geschwindigkeit gibt es keine merkbaren Verzögerungen beim Aufruf einer Seite.
D.h., ich bin vollkommen zufrieden.
Nochmals Danke an alle!
Dennoch werde ich die weitere Diskussion mit Interesse verfolgen, wenn gleich ich bei den letzten Beiträgen immer weniger verstehe. Spannend ist es aber auf jeden Fall.
Beste Grüße
Mathematiker
Horst_H - Do 14.02.13 09:08
Hallo,
dann ist aes ja gut, dass es schneller als google ist ;-).
Aber, die Hash-Funktino ist nicht meine Idee
AVL-Baum ist nur schneller gegenüber linearer Liste, wenn man während des Einfügens sortiert bleiben will. Wenn man alles einliest und anschliessend sortiert, wird binäre Suche vom Aufwand her schneller sein.Man kann sogar eine sortierte Liste speichern ;-)
Gruß Horst
Martok - Do 14.02.13 18:06
Oha. Ich und BigO :lol:
| Xion hat folgendes geschrieben : |
| Martok hat folgendes geschrieben : | | binäre Suche auf sortierter Liste |
Das fasziniert mich. Kannst du mal kurz skizzieren, wie das geht? Typischerweise kann man bei Listen nicht in O(1) auf ein bestimmtes (das mittlere) Objekt zugreifen. |
Nicht in verketteten Liste, klar. Da ists O(n/2), klar (falls man die Anzahl separat mitzählt). Aber wer will auch verketten, wenn man nicht muss ;) Auf Arrays ist jeder Zugriff O(1)...
Damit wird die gesamte Suche:
| Xion hat folgendes geschrieben : |
| Komplexität O(logn) |
Aber wenn man unbedingt was verkettetes braucht, gibt's immer noch SkipListen. Wenn man die passend verdrahtet, könnte das auch gehen. Da würde man dann die Skips als so eine Art BTree setzen. Glaube ich :gruebel:
| Xion hat folgendes geschrieben : |
| also deutlich schlechter als O(1) für die Hashtable. |
Da hast du aber nur 1/3 berechnet:
Hash berechnen: O(stringlänge)
Bucket finden: O(1) falls das ein Array ist, bei größerem Keyspace wirds wohl eine Sparselist, die ist langsamer
Eintrag in Bucket suchen: O(m) oder O(logm), je nachdem was da drunter hängt...
Xion - Do 14.02.13 19:47
| Martok hat folgendes geschrieben : |
| Aber wenn man unbedingt was verkettetes braucht, gibt's immer noch SkipListen. Wenn man die passend verdrahtet, könnte das auch gehen. Da würde man dann die Skips als so eine Art BTree setzen. Glaube ich :gruebel: |
Du hattest was von InsertionSort und binärer Suche erzählt. Für InsertionSort in O(1) ("sofort") braucht man ja verkettete Listen. Und das dann mit binärer Suche... :)
Ok, SkipListen kannte ich noch nicht, aber das Vorgehen ist logisch. Vielleicht würde das tatsächlich gehen, aber man müsste diese "Skips" immer wieder reparieren...weil wenn man einen Eintrag löscht oder einfügt, dann ist die Mitte ja nicht mehr die Mitte ;) Einfügen wäre wohl dann O(logn)
| Martok hat folgendes geschrieben : |
Da hast du aber nur 1/3 berechnet:
Hash berechnen: O(stringlänge) |
Das stimmt.
| Martok hat folgendes geschrieben : |
| Eintrag in Bucket suchen: O(m) oder O(logm), je nachdem was da drunter hängt... |
Eigentlich sollte die Hashtable so groß sein, dass es keine Kollisionen gibt. Bei Mathematiker waren es ja nur 5 Elemente, bei denen eine Kollision vorkam. Das m wäre also etwa 5/16000 ;) (im Durchschnitt)
Also wenn man grob genug ist, kommt für die Hashtable schon O(1) hin ;) Wir haben aber auch Algorithmen gehabt, bei denen man sagt, der braucht O(2^100+logn) = O(logn) :mrgreen: Die Notation ist nicht immer ganz praxisnah :P
Martok - Do 14.02.13 20:19
| Xion hat folgendes geschrieben : |
| Du hattest was von InsertionSort und binärer Suche erzählt. |
Da hatte ich mich wohl irgendwo selbst überholt :roll:
| Xion hat folgendes geschrieben : |
| Martok hat folgendes geschrieben : | | Eintrag in Bucket suchen: O(m) oder O(logm), je nachdem was da drunter hängt... |
Eigentlich sollte die Hashtable so groß sein, dass es keine Kollisionen gibt. Bei Mathematiker waren es ja nur 5 Elemente, bei denen eine Kollision vorkam. Das m wäre also etwa 5/16000 ;) (im Durchschnitt) |
Um den Preis von hohem Speicherverbrauch. 16bit Keyspace mit je 4byte Daten sind 256kByte, das geht ja noch. Bei 32bit sind das dann schon 16GByte...
Wobei das dann auch wieder ein anderes Verfahren ist.
WP sagt [
http://en.wikipedia.org/wiki/Hash_table#Separate_chaining], das was du meinst heißt dann "dynamic perfect hashing". Ich kenn keinen, der das freiwillig für General-Purpose Klassen nimmt ;) Das was ich meine ist eine "array hash table". Kann man natürlich auch gern mit einer TList bauen, ist meistens einfacher.
Ging es in diesem Thread eigentlich um die effizienteste Speziallösung für das konkrete Problem oder was Allgemeines? Kann nämlich durchaus sein, dass ich hier Zeug meine, was gar keinen interessiert :D
OT:
MurmurHash [
http://code.google.com/p/smhasher/wiki/MurmurHash3] wär auch noch was, falls die KeyStrings viel länger werden (und so viele, dass man nicht einfach auf 1-2 Bytes runter-XORen kann, sondern die perfekte Verteilung im Keyspace braucht). Implementation in Delphi existiert, aber ohne Testvector etwas schwierig. Muss bei Gelegenheit mal die Testsuite portieren.
Xion - Do 14.02.13 20:31
[quote="
Martok"(673345)]
| Xion hat folgendes geschrieben : |
| Wobei das dann auch wieder ein anderes Verfahren ist. WP sagt [http://en.wikipedia.org/wiki/Hash_table#Separate_chaining], das was du meinst heißt dann "dynamic perfect hashing". Ich kenn keinen, der das freiwillig für General-Purpose Klassen nimmt ;) Das was ich meine ist eine "array hash table". Kann man natürlich auch gern mit einer TList bauen, ist meistens einfacher. |
Ich meine das dort erwähnte Open addressing. Statt Buckets mit Listen suche ich mir einfach deterministisch ein neues freies Slot. Das ist auch nicht schneller als mit Buckets, aber wie auch dort erwähnt, sollten pro Bucket sowieso nur max. 3 Elemente drin sein. Fällt also aus der O-Notation raus ;)
| Martok hat folgendes geschrieben : |
| Ging es in diesem Thread eigentlich um die effizienteste Speziallösung für das konkrete Problem oder was Allgemeines? |
Ich denke es ging um eine Speziallösung. Das Thema ist aber eigentlich schon gelöst, und ich werde mich jetzt auch zurückhalten. Versprochen :zwinker:
Mathematiker - Do 14.02.13 20:42
Hallo,
| Martok hat folgendes geschrieben : |
| Ging es in diesem Thread eigentlich um die effizienteste Speziallösung für das konkrete Problem oder was Allgemeines? Kann nämlich durchaus sein, dass ich hier Zeug meine, was gar keinen interessiert :D |
Auch wenn ich nichts alles verstehe, ist es meiner Meinung nach hochinteressant. Und Lernen kann man bei Euren Beiträgen eine Menge.
| Xion hat folgendes geschrieben : |
| Ich denke es ging um eine Speziallösung. Das Thema ist aber eigentlich schon gelöst, und ich werde mich jetzt auch zurückhalten. Versprochen :zwinker: |
Warum? Wie gesagt, mich interessiert dies sehr und ich denke auch andere.
Allein schon die Vielzahl der Möglichkeiten, so ein Suchproblem effektiv umzusetzen, ist faszinierend.
Beste Grüße
Mathematiker
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!