Große Strings schnell auf Inhalt einer Zeichenkette prüfen?

[romber]

Hallo!

Gibt es eine ressourcenschönende schnelle Methode, sehr große Strings (wie in meinem Fall eine TStringList mit über 250.000 ziemlich langen Einträgen) auf Existenz einer bestimmten Zeichenkette zu prüfen? Mit pos geht das zwar auch, so richtig schnell ist das aber nicht.

Danke!

[SirThornberry]

also pos ist bereits in assembler programmiert und is somit wohl nur sehr schwer noch zu optimieren (wenn überhaupt möglich). Wie genau verwendest du es in Zusammenhang mit einer Stringlist? Suchst du in der Stringlist nach kompletten Einträgen? Wenn du suchst welcher Index in der Stringlist mit einer bestimmten zeischenkette los geht hilft es schon die Stringlist zu sortieren und dann den algorythmus darauf anzupassen, ansonsten wenn es darum geht einen teilstring an beliebiger Stelle zu finden dann bleibt nur übrig das du alle items der Stringliste durchgehst und das dauert nunmal lange..

[romber]

Danke für schnelle Antwort!

Ich habe Einträge, die aus Zahlen bestehen. Hier ein kleiner Abschnitt des Inhaltes:

...
33670903
33670905
33670899
33670911
33670915
33670904
33670919
33670920
33670912
33670916
33670921
33670918
...

Mann kann da erkennen, dass die Zahlen immer höher werden, aber nicht immer in der richtigen Reihenfolge sind. Ich möchte eigentlich nur sehr schnell prüfen, ob der eintrag bereits in der Liste ist, bevor ich diesen hinzufüge. Kann man da was optimieren?

[Ultimator]

Und wenn du mit IndexOf hergehst, und den zurückgegebenen Index auf -1 überprüfst?

[alzaimar]

Wenn Du statt einer Stringlist einfach einen String nimmst (und nicht einfach sl.Text verwenden, weil lahm), dann sollte Boyer-Moore deinen Anforderungen genügen. Wenn der String nur am Anfang einer Zeile stehen kann, wäre eventuell eine individueller Algorithmus schneller. Allerdings berücksichtigt Boyer-Moore auch diesen Sonderfall (man sucht dann einfach nach "#10#13FooBar").

Besorge Dir FastStrings.Pas von hier
http://www.droopyeyes.com/default.as...owProduct&ID=4

Alternativ empfehle ich mein TStringDictionary, eine dynamische Hashliste. Es fügt 100.000 Strings inkl. überprüfung in 600ms ein. TStringList ist 2-100x langsamer (je mehr Strings, desto schlimmer). Dafür verzichtest Du auf eine Sortierung. Wenn Dir das schnurz ist, verwende mein Wörterbuch.

[SirThornberry]

wenn es nur zahlen sind würde ich nicht die Stringlist nehmen sondern direkt TList und anstelle von Pointern deine Integer da rein hängen (casten). Dann das ganze noch sortieren und dann solltest du mit dem Quicksortalgorythmus recht schnell herausfinden ob der Eintrag schon vorhanden ist. Falls du bei der Stringlist bleibst so ist dort Sorted schon implementiert und auch IndexOf.
Wenn sorted auf True ist und "duplicates" auf "dubExcept" so bekommst du einen Fehler wenn du einen vorhandenen Eintrag adden willst (das ganze in Try-Except) und du solltest recht schnell fertig sein.

[alzaimar]

Auch da sind Hashlisten einfach schneller. Ein TIntegerDictionary ist im geposteten Sourcecode enthalten. Er ist gegenüber einer TList, Sortieren und Binarysearch auch um den schon erwähnten Faktor schneller.

Das 'Suchen' von Daten sollte und muss keine Zeit kosten. Natürlich immer relativ. Bei 100.000.000.000 Datensätzen darf das Suchen ruhig mal mal 100ms dauern, da doch einige Festplattenzugriffe nötig sind (bei einem B-Baum wären das ca. 3 Zugriffe a 8kb). Bei bis zu 10.000.000 Datensätzen, die ich ohne Probleme im Speicher halten kann, ist eine Hashliste optimal

[romber]

Ich wollte die vom Alzaimar entwickelte TIntegerDictionary probieren und habe ihn um einen Beispiel gebeten. Er hat mir die Beispielcode und die bereits erstellte EXE-Datei geshickt. Wenn man die Datei ausführt, wird in einem Memo-Feld angezeigt, wie lange den Suchprocess gedauert hat. Und das geht wirklich verdammt schnell. Ich habe jetzt aber ein anderes Problem: sobald ich die Code ins Delphi lade und ohne etwas zu ändern von dort ausführe, wird das Programm um fast deppelt langsammer! Woran liegt das?

[himitsu]

Führe dein Programm mal ohne Debugger aus ... also nicht direkt vom Delphi aus.
Der Debugger bremst ein wenig.

Ich hatte z.B. mal den Fall, daß ein reiner ASM-Code im Debugger mindestens 20-mal Langsamer ablief, als ohne.





Du könntest eventuell auch mal nach meinem SearchSameFiles (unter Open Source) suchen, dort werden zwar Dateien verglichen, aber man kann den Code auch leicht dahingehend verändern, daß da Strings verglichen werden.

Es wäre zumindestens ein "nettes" Beispiel für dich.

Dort wird mit 'ner Hashliste gearbeitet und bei gleichem Hash sicherheitshalber nochmals die Dateien(oder Strings) verglichen und da die Hashs nicht sortiert sind gibt es noch 'ne abgeänderte Pos-Funktion zum suchen eines Hashs.

PS: wunder dich aber nicht, wenn sich das Programm so nicht compilieren läßt ... dir fehlen da bestimmt noch ein paar Dateien eines anderen Projekts, aber wenn nötig kann ich dir ja die entsprechenden Funktionen/Proceduren noch zukommen lassen (und einige davon sind auch schon in der DP veröffentlicht)

[sniper_w]

Bei einer Sortierte Liste ist Binary Search seeeehr schnel....
Man braucht maximal 32 mal abzufragen in einer List von 2^32 Beiträgen um eine richtige Antwort zu bekommen. Da sollte es Geschwindigkeitsvorteile schon geben...

google.com ;)

[himitsu]

@sniper_w: dann müßte er die Werte (Hashs) aber auch erstmal sortieren, was natürlich auch zeit verbraucht.
z.B. ist es in meinem SerarchSameFiles einfacher gewesen die unsortierte Lsite zu durchsuchen, als ständig darauf zu achten, daß die Liste sortieret ist, da sich meine Liste ständig verändert.
(außerdem ist es dort eh nicht so einfach möglich die Liste der größe nach zu sortieren, da ja schon eine andere Sortierung vorhanden ist)

Aber was er nun macht, ist ja nur ihm selber überlassen ^^

[alzaimar]

Zitat:

Zitat von sniper_w

Bei einer Sortierte Liste ist Binary Search seeeehr schnel....

Alles ist relativ.

Bei einer Hashliste dauert das Suchen in 100.000.000 Elementen genauso lang, wie das Suchen in einer Liste mit 1.000 Elementen. Mit Binary seach ist das Verhältnis 3:1 na, nun.

Das EINFÜGEN (denn die Elemente müssen ja erstmal rein) dauert bei Hashlisten von 100.000.000 Elementen für das letzte Element genau so lang, wie für das erste. Bei einer sortierten Liste ist das nicht so. Für jedes Element muss ich die Position suchen und Platz im Array schaffen (zur Not alle N Elemente verschieben). Und DAS dauert, nämlich je mehr Elemente desto länger. Besser als sortierte Liste sind hier allemal unsortierte Listen, die nach den Einfügeoperationen einmalig sortiert werden. Diese sind aber nicht allgemein zu verwenden. So kann man z.B. damit nicht effizient das Problem von romber lösen.

Bäume, insbesondere die beliebten AVL oder Red/Black-Trees sind da schon besser, allerdings geht so viel Zeit für das Ausbalancieren flöten, sodas sie bei grossen Datenmengen auch performancetechnisch wegschmieren. Sie liegen in der Performance aber vor den sortierten Listen.

Die Performanceunterschiede sind so gewaltig, das bei zeitkritischen Anwendungen sortierte Listen, Bäume etc. nicht in Betracht kommen. Hier haben sich einzig und allein Skiplisten und Hashlisten als praxistauglich erwiesen: Skiplisten sind etwas schneller bei < 50.000-500.000 Elementen (je nach zu vergleichendem Datentyp), Hashlisten spielen ihre Überlegenheit i.A. bei sehr großen Listen aus.
Das berechnen eines Hashwertes für Strings ist mit einem gewissen Zeitaufwand verbunden. Eine Skipliste verwendet nur einfache Stringvergleiche, die auf heutigen CPU mit einem Befehl abgearbeitet werden. Daher der Vorteil der Skiplists, obwohl mehrere Vergleiche nötig sind, um ein Element zu finden. Bei sehr vielen Elementen ist die Lookupinformation in einem Skiplistknoten 'voll', also degeneriert die Liste etwas (eignet sich aber trotzdem immer noch als Kandidat für den Weltmeistertitel!)

Ich poste heute Abend (unter einem eigenen Thread) mal ein kleines Proggi, das Listen, Bäume, Hashes und Skiplisten performancetechnisch vergleicht (so richtig mit Chart und angeben und so ;-). Ich hoffe, dieser Thread wird dann rege besucht und das Programm um weitere Listen erweitert, und vor allen Dingen, die bestehenden Listenklassen werden optimiert.

@himitsu: Hashlisten werden nicht sortiert, das ist ja das Tolle. Im Prinzip funktioniert eine Hashliste so:

Code:

Einfügen (Schlüssel)
  I := KeyToIndex (Schlüssel)
  HashListe[i] := Schlüssel;

Suchen (Schlüssel):
  I := KeyToIndex (Schlüssel)
  If HashListe[I] = Schlüssel then 'gefunden' else 'nicht in der Liste'

Natürlich ist das 'etwas' komplexer, aber im Prinzip bilde ich den Schlüssel auf einen integer so ab, das das Resultat genau dem Index einer Liste entspricht. In der Praxis gibt es so eine Funktion natürlich nicht, sodass es vorkommt, das zwei Schlüssel auf den gleichen Index abgebildet werden->Kollision. Nun gibt es diverse Strategien, um eine Kollision aufzulösen. Geh mal zu Wiki und schau nach, is ganz gut beschrieben.

[edit]: Und wenn Du so ein Programm schreiben willst, das doppelte Dateien findet, na dann ist die TStringDictionary genau das richtige für Dich[/edit]

[himitsu]

Ich hab in meinem Proggi einen 32-Bit-Hash (CRC32 ... sowas wie MD5 mir zu blöde, und bei 32-Bit man die maximale Hashgröße, die sich auch noch am leichtesten suchen läßt).
Und ich hab ja gesagt, daß ich die Hashliste nicht sortiert hab (jedenfalls nicht so, wie es für ein Binary Search nötig wäre)
Also nach deinem Beispiel hat jeder Hash einen Index?
Wenn ich also am einfachsten für jeden Hash ein Bit reserviere, dann brauch ich aber massig RAM -.-''
Wie will man da also 'ne Liste mit den Index erstellen?

Aber erstmal egal ... mal sehn was sein Tut dazu sagt :roll:

[alzaimar]

Man muss unterscheiden zwischen einer Hashliste, was eine Datenstruktur ist, und einer Liste von Hashes, was einfach eine Liste von Abkürzungen für irgendwelche Dingsels ist. Z.B. kannst du eine Liste von Hashwerten aller Dateien nehmen.

Hier ist aber eine Hashliste, Assoziativ-Array, Dictionary gemeint.

[himitsu]

Aso -.-''

Aber dann muß ja dennoch in der assotiativen Liste nach dem Hash gesucht werden ... also einen Vorteil kann ich dann darin nicht erkennen -.-''

[alzaimar]

himitsu: Nee :zwinker:
KeyToHash ('Müller') ---> 12345. Unsere Liste hat genau 1000 Elemente, also 12345 mod 1000 = 345.
Also ist der Record zu 'Müller' in Hash[345]. Da is nix mit Suchen! Wie gesagt, wenn KeyToHash('Meier')=22345 ergibt (mod 1000 = 2345!), dann haben wir hier ein Problem = Kollision, da muss man sich dann was ausdenken. Warte einfach ne Stunde, dann poste ich meinen Vergleich. Ich schick dir ne PN (wenn mein Alzheimer-Hirn mich nich im Stich lässt :stupid: ).

[himitsu]

Also verkleinerst du einfach den Hash, -.-''
na wenn das so ist, dann würde ich doch gleich 'nen CRC16 verwenden.
Da wird dann kein MOD, oder so, benötigt und man kommt locker mit 'ner 8/256 KB-Liste hin :)

8 KB nur für 'ne Bitliste > Wert gibt es schon, oder nicht
und 256 KB für 'ne Liste mit Pointern.

Aber wie gesagt, so ein Code wie z.B. bei mir hat auch keinerlei Probleme mit doppelten, oder noch mehr Vorkommen eines selben Hashs :mrgreen:
(na ja... mal sehn was da veröffentlich wurde ^^)

[alzaimar]

CRC16 geht doch nur bis max. 65536 Elemente. Was ist bei 10.000.000 Elementen?

[Der_Unwissende]

Bin mir nicht sicher wie schnell sie ist, möchte aber mal auf die THashedStringList (ich denke uses IniFiles oder so) verweisen. Da kümmert sich Delphi wohl um die optimale Hash-Länge und das Ding ist im Verhältnis zur normalen String-List auch mal gut schneller.
Natürlich sollte auch hier sortiert eingefügt werden um die Suche optimal zu gestallten, aber muss halt mal jmd. gucken ob es auch ohne geht und wie groß der zeitliche Aufwand für normal eintragen + Suchen bzw. sortiert Eintragen + Suchen ist.

[alzaimar]

Ich habe sie getestet, bringt in diesem Fall nur bis <20.000 etwas, dann ist sie beim Suchen besser als eine normale Stringlist.
Ich verweise mal auf meinen Thread, indem diverse Listen verglichen werden. Ich baue die mal da ein.

[himitsu]

Zitat:

Zitat von alzaimar

CRC16 geht doch nur bis max. 65536 Elemente. Was ist bei 10.000.000 Elementen?

Ist mir wohl bekannt.

Nur hast du in deinem "Beispielchen" doch einen größeren Hash mittels "mod 1000" in einen Kleineren gesplittet.

Wozu also erst einen Größeren Wert (was meist auch noch rechenaufwendiger ist) erstelen, wenn dieser dann eh in 'nen Kleineren umgewandelt wird?

Und in diesem Vergleich ist CRC16 also schneller und hat immernich einen Größeren Werteumfang, als die mit "mod 1000" erstellten 1000 verschiedenen Werte.

[alzaimar]

Meine Hashtabelle vergrößert sich doch dynamisch.

Ich hatte ursprünglich auch den CRC16 drin, bis ich meine StringDictionary für mehr als 655536 Elemente brauchte. Also den CRC32.
[edit] Und die Berechnung von CRC32 ist auch nicht langsamer, als CRC16. [/edit] Dann habe ich noch recherchiert und, siehe da, es geht noch schneller: Ich habe den 'ELF'-Hash verwendet, daneben gibt es noch den 'Pjw', der in Compilern Verwendung findet. Ich hatte mal ELF und PJW verglichen, bin dann bei ELF hängengeblieben.

Also nochmal (auf die Gefahr hin, das Dich das nervt):
Ich berechne einen 32bit-Hash zu dem einzufügenden Schlüssel. Damit bin ich, was die maximale Größe der Liste anbelangt, auf der Sicheren Seite. Bevor ich die aber gleich so gross mache, fange ich ganz klein an, nämlich bei 1000 (genauergesagt 997, weil Primzahl) an. Wenn die Liste langsam voll wird, muss ich sie vergrößern. Ich verdopple also die Größe, such mir die nächstbeste Primzahl und dass ist dann die neue Listengröße. Natürlich muss ich einmalig alle bereits in der Liste gespeicherten Elemente nochmals in die neue, größere Liste einfügen, da sich ja die Hashfunktion (ELF mod ListSize) verändert hat. Ich dachte zuerst, dass damit die Performance flöten geht, aber nee. Ausserdem kommt das 'Rehashing' sehr selten vor, bei 2^32 einzufügenden Elementen passiert das ja nur 20 mal, oder so.

Ich verwende Stringlisten derzeit nur noch ihrem Zweck (LISTEN) entsprechend. Wenn ich aber nach Strings suchen muss, geht nix über eine Hash-Tabelle (oder gleich eine DB). Na gut, die Skiplist ist für kleinere (<40.000) Elemente noch etwas besser, aber ich mag die Stringdictionaries nun mal. Vielleicht, weil ich sie mir selbst gebastelt habe.

[shadowman]

Hallo zusammen,
wie benutzt man diese Hash-Tabellen (TStringDictionary) denn? Ist von der Handhabung her anders als TStringList, oder? Ich komme damit irgendwie nicht zurecht. Z.B. weiß ich nicht, wie ich auf einzelne Zeilen zugreifen kann und deren Inhalt.
Mit TStringListe konnte man das mit Liste.Strings[Index] zugreifen. Mit TStringDictionary geht das z.B. nicht usw.

Hier stand irgendwo, dass ein kleines Beispiel-Projekt per Mail geschickt wurde. Könnte jemand (alzaimar ?) vielleicht ein Beispiel hier posten, damit alle was davon haben? Wie man das Ganze nutzt:
- Einträge "richtig" einfügt (falls da was zu beachten gibt)
- durchläuft
- auf bestimmte Einträge/Zeilen zugreift usw.
- ...

Wäre sehr nett.

Gruß und frohe Ostern Euch!
shadow

[Elvis]

Schaue mal hier vorbei. (Beitrag 6)
Funktioniert für Strings fast genau wie für Integers. ;)

[shadowman]

Hallo Elvis,
danke sehr für die Antwort und den HInweis, allerdings bin ich dadurch nicht so richtig schlauer geworden :oops:

Delphi-Quellcode:

Var
   Liste: TStringDictionary;
   i: integer;
begin
   Liste := TStringDictionary.Create;

   for i := 0 to 99 do begin
      Liste.Add('Mustertext' + IntToStr(i), nil); // mit nil geht es schon los.. wieso, weshalb, warum?
   end;

   // wie gehe ich nun z.b. zu der Zeile 77 und zeige mir diese an oder mache damit irgendwas?
   // bei einer StringList wäre es: ShowMessage(Liste.Strings[77]);
   // wie ist das bei der HashListe?
   
end;

Gruß,
shadow

[Elvis]

Du hast anscheinend nicht gelesen wie alzaimar versucht hat, himitsu Dictionaries zu erklären...

Man benutzt ein Dictionary NICHT als normalen Datencontainer. Wie der Name schon sagt ist es zum Nachschlagen da...

[alzaimar]

Ahoj,

zurück aus dem Osterurlaub!

Eine Dictionary ist ein Wörterbuch. In einem Wörterbuch ist zu einem bestimmten Wort etwas hinterlegt, z.b. eine Erklärung, eine Übersetzung oder ein Bild.

Ich kann Wörterbücher also dazu verwenden, um zu einem Schlüssel irgendwelche Informationen zu speichern. Ich kann ein Wörterbuch aber auch dazu verwenden, um doppelte Vorkommen eines Schlüssels auszuschließen. Dann speichere ich einfach Nichts (oder Nil) zu dem Wort. Wenn ich wissen will, ob ich ein 'Wort' schon einmal gespeichert habe, kann ich nun einfach im Wörterbuch nachschauen, ob das Wort drinsteht. Nur wenn es nicht drinsteht, füge ich es ein (denn dann hab ich es ja wohl vorher noch nicht gesehen). Man verwendet Hashtabellen z.B. beim Parsen. Im 'Procedure'-Wörterbuch kann ich sicherstellen dass erstens eine Prozedur nicht 2x implementiert und zweitens eine Prozedur definiert wird, bevor sie aufgerufen wird.

Der fundamentale Unterschied zwischen einer Liste und einem Wörterbuch ist die beim Wörterbuch fehlende Möglichkeit, die enthaltenen Daten aufzulisten, womöglich auch noch sortiert. Man kann natürlich alle Daten durchiterieren, das hat die von mir entwickelte Klasse, aber das ist eine -im Vergleich zur Liste- relativ lahme Krücke. Dafür ist sie beim Einfügen und Suchen verdammt schnell.

In einer Hashtabelle ist es egal, ob 100 oder 100.000.000 Wörter gespeichert sind: Die Suche geht immer gleich schnell. Bei einer Liste warte ich mir bei 100.000.000 Elementen einen Wolf ;-)