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.

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.

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: www.minorplanetcente...u/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

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.

Beste Grüße
Mathematiker

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.

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

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!

Horst_H hat folgendes geschrieben :

schade das Mathematiker bei Delphi 5 bleiben will

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. 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.
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

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.

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:
scrabble-dictionary-...esources/enable1.txt

Ausgabe


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

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.
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

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.

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:


Gruß Horst

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

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?

Die Seitenzahl wäre toll, wenn man zu einer Seitenzahl den Begriff sucht

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

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

Zitat:

Menge Menge (2)

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.

Beste Grüße
Mathematiker

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.

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

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 ). Ich denke AVL bringt da keine Vorteile. Die Implementierung ist dafür schön knifflig .

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

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

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