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

[alzaimar]

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]