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

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