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

[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 ;-)