Vergleich von Suchverfahren mit Beispielen

[alzaimar]

In Anbetracht der häufig gestellten Fragen nach 'Suchen in einer Liste' und Ähnlichem hab ich mal vier Verfahren verglichen:
- Stringlist
- AVL-Baum
- Skiplist
- Hashlist

Das Testprogramm fügt zunächst Werte in die jeweilige Datenstruktur ein und sucht sie anschließend wieder. Beim Einfügen wird sichergestellt, das der Eintrag nicht schon in der Liste ist.

Ich würde mich freuen, wenn Jemand einen schnelleren Algorithmus/Datenstruktur findet oder die vorhandenen verbessert. Falls jemand andere schnelle Verfahren hat, dann kann er sie hier posten bzw. das Testprogramm erweitern.

[edit] Update: Auf Nachfrage wurde die THashedStringList aus IniFiles von Borland mit aufgenommen. Neu ist auch, das man angeben kann, ab welcher Dauer eine Reihe während des Messlaufes nicht weiter verfolgt werden soll. Das Laufzeitverhalten einiger Listen degeneriert bei grossen N. Wenn also die Messung des Einfügens einen bestimmten Wert, wird das Verfahren nicht weiter berücksichtigt: Damit man sich keinen Wolf wartet [/edit]

[edit] Update: THashedStringlist wurde mit 'Sorted := True' instantiiert und dadurch unnötig langsam[/edit]

[jfheins]

Nett .. wenn du jetzt nochmal die Verfahren kurz erklären würdest (Dictionary = Stringlist ???)

Was mir aufgefallen ist: Warum hat die blaue Kurve so Zacken, als wäre sie z.B. mit 500.000 langsamer als mit 1.000.000 ? :gruebel:

[alzaimar]

Stringlist= Delphi TStringlist mit Sorted := True und Duplicates := dupIgnore, Suchen per binary search
AVL - Tree: AVL-Baum (Binärer ausgeglichener Baum)
Skiplisten: Verkettete Listen mit zusätzlichen Pointern auf weiter entfernte Elemente (Skip list)
Directories : Hash tabellen (Nein. Nicht zum Rauchen)

Zitat:

Zitat von jfheins

Was mir aufgefallen ist: Warum hat die blaue Kurve so Zacken, als wäre sie z.B. mit 500.000 langsamer als mit 1.000.000 ? :gruebel:

Wenn Hashtabellen voll sind, werden sie erweitert. Due Größe der vergrößerten Tabelle eine Primzahl, die ungefähr doppelt so gross ist, wie die ursprüngliche Tabelle. Es scheinen 'gute' und 'schlechte' Größen zu geben. Einige sind 'mies'. Warum das so ist, weiss ich nicht.

[Der_Unwissende]

Hey,
was ich ein wenig vermisse ist die gute THashedStringlist. Gab es da einen guten Grund sie nicht mit zu berücksichtigen? Also sonst würde mich die auch noch in deinem Test interessieren, zumal die echt gut schneller ist als die TStringlist und ich würde mal denken, dass da Borland für sorgt, dass immer gute Werte für's Hashen benutzt werden.
Ansonsten nettes Programm!

Gruß Der Unwissende

[alzaimar]

Hi,
Danke für den Tip. Ich hab sie mal eingebaut Im 1.Posting kann man die neue Version laden. Sie misst nun auch nur das Suchen.

[stoxx]

zu den Skiplisten ... hier eine richtig geile Seite mit Vorlesungs Videos !
wow .. da tut sich was an den Unis :-)

http://electures.informatik.uni-frei...2004&chapter=7

[mschaefer]

Moin, moin,

Das ist eine schöne Gegenüberstellung, die einem
viel Arbeit in die falsche Richtung ersparen kann.

Grüße nach Berlin

[hathor]

Hi,

Dictionary ist deutlich am Besten!

Kennt jemand die Media Library von WINAMP?
Da gibt es MAIN.IDX und MAIN.DAT (und einige andere) - gibt es einen DELPHI-Sourcecode, mit dem man auf die Datenbank zugreifen kann?
Mit welchem Datenbankmodell ist sie vergleichbar?

Danke für jede Hilfe!

[abrosda]

Der AVL Tree wird erheblich schneller, wenn nicht jedesmal vor dem einfügen geprüft wird, ob der Key schon im Baum vorhanden ist.
Das setzt natürlich eindeutige Werte voraus.

[Dezipaitor]

wo ist der B(*/+)-Baum ? :D

[alzaimar]

Der B-Baum ist eine Mischung aus T-ärem Baum und Binary Search, wird also in der Performance irgendwo dazwischen sein.
Desweiteren ist der BB für Daten gedacht, die sich auf einem externen Datenträger befinden, und passt deshalb vom Konzept her hier nicht rein.

Ich vermute auch, das der Overhead etwas zu hoch ist, um mit reinen in-Memory-Lösungen mithalten zu können.

[Dezipaitor]

Die Suche/Einfügen/Löschen ist in einen B-Baum mit b-Einträge pro Knoten in schlechtesten Fall in O(b_log n) Schritten geschafft. Der B+ Baum hat sogar den Vorteil, dass nur die Blätter echte Daten enthalten und in einer linearen Liste verkettet sind, so dass eine Speicherung nur O(n) Speicherplatz braucht.

Dieses Video zeigt, wie ein B-Baum erstellt wird
http://youtube.com/watch?v=coRJrcIYbF4

Also warum sollte so ein Kunststück fehlen sollen?

[mschaefer]

Zitat:

Zitat von Dezipaitor

Also warum sollte so ein Kunststück fehlen sollen?

Ohne übermäßig zu Lästern würde ich es mal so beantworten: Weil Alzeimer vielleicht keine Zeit hat und Du es nicht umsetzen magst (kannst?).
Gib Ihm kein Viedeo sondern Deine Implementierung und er baut es bestimmt ein.
Aber ich gehe davon aus, dass er keine schnellere Variante sein wird (gerade in gut gecachten Rechnern).

Grüße // Martin

[alzaimar]

Zitat:

Zitat von Dezipaitor

Also warum sollte so ein Kunststück fehlen sollen?

Ich schrieb doch bereits, das das der Bayer-Baum nicht hier herein passt, da es sich nicht um eine generische Struktur bzw. Algorithmus zum schnellen Speichern von Assoziationen in-Memory handelt. Der Bayer-Baum wurde doch vor allen Dingen für Page-I/O entwickelt, daher die Seiten konstanter Größe.

Im Übrigen benötigt man doch kein Video, um einen Algorithmus zu verstehen. Ein gutes Buch reicht.

Wie wäre es, wenn Du, Dezipaitor, eine B*-Baum-Klasse implementierst und in den Testcode einpflegst? Ich behaupte immer noch, das der Overhead der Seitenverwaltung zu viel Performance klaut. Und gegen eine Hashmap, Skiplist oder einen Trie (DAWG) kommt der BB-Monolith eh nicht an. Natürlich lasse ich mich gerne eines Besseren belehren. Du kannst den Code von Julian Bucknall als Grundlage verwenden, er schwirrt in den Tiefen des WWW irgendwo herum.

Bei der Gelegenheit könnte man auch einen DAWG mit aufnehmen, nur frisst so eine Datenstruktur dermaßen viel Speicher, das sie den Test nicht besteht. Dafür wäre ein DAWG schneller als ne Hashmap.

Wie gesagt, es ging mir nicht um eine vollständige Liste von Listenstrukturen und deren Performancevergleich. Ich habe einen schnellen in-Memory-Cache für einen Interpreter benötigt, und da ging eben die Analyse los. Letztendlich bin ich bei der Hashmap hängengeblieben, aber nur deshalb, weil ich das Verfahren verstanden habe. Die Skiplist habe ich im Zusammenhang mit dem Sourcecode des MS SQL-Servers kennengelernt und wollte nur mal wissen, was ist. die AVL Bäume kenne ich noch aus meiner Studienzeit und -na ja- binary search lernt man in der Schule.

@mkinzler: Ich hab hier irgendwo eine B-Tree-Klasse rumliegen, aber wozu soll ich die einbauen (s.o.)? Wer will, kann das gerne selbst machen. Ich hab doch nicht das Monopol auf die Testumgebung.

[abrosda]

Ich werd' mal sehen, ob ich vor Weihnachten ein bischen Zeit an meinem Rechner zu Hause habe und dann noch ein paar Algorhithmen hinzufügen. Interessant ist ein Vergleich zwischen den Stringvergleichen und Integervergleichen...

[alzaimar]

Zitat:

Zitat von abrosda

Interessant ist ein Vergleich zwischen den Stringvergleichen und Integervergleichen...

Yo, gute Idee.

Vermutlich wird die Hashmap ggü. der Skiplist besser abschneiden, da bei der Hashmap (=Dictionary) der String per Hash-Funktion in einen Integer umgewandelt wird. Anschließend finden (fast) nur noch Integer-Vergleiche statt.

In allen anderen Strukturen wird dagegen der zu suchende Text stehts mit einem Schlüssel verglichen.

[mquadrat]

So, ich hab jetzt auch mal ein bisschen mit den Listen rumgespielt. Für den ein oder anderen vielleicht interessant: Wenn man bei der THashedStringlist die Sortierung weg lässt kann man für kleinere Datenmengen nochmal Geschwindigkeit rauskitzeln. Erst ab 50.000 Einträgen wird das Suchen extrem langsamer. Davor ist zwischen sortierten und unsortierten THashStringlists kaum ein Unterschied beim Suchen.

[alzaimar]

Das ist interessant! Hast Du deine Optimierung mal in die Teststruktur eingepflegt, sodaß man unmittelbar einen Vergleich mit den anderen Datenstrukturen ziehen kann?

Immer wieder wichtig ist zu wissen, ob und wie eine Datenstruktur skalierbar ist, ob sie also auch bei exorbitanten Datenmengen noch performant ist. Wenn man es braucht.

[Luckie]

@alzaimar: Wenn du alles zusammen hast, mach doch daraus ein Tutorial und poste es in der Tutorialsparte.

[Oreaden]

@Luckie: Feine Idee ein Tutorial zum Thema, wie erstelle ich eine Testumgebung

Hab da noch nichts gefunden und meine Kristallkugel läßt mich zu diesem Thema auch in Stich :roll:

Schöne Grüße
OREADEN

[alzaimar]

Im Code der Testsuite hatte sich eine kleine Nachlässigkeit eingeschlichen, die mquadrat entdeckt hat. Eine überarbeitete Version ist im 1.Post zu finden.
Puh, für ein Tutorial über die Datenstrukturen fehlt mir im Augenblick die Zeit, da die Thematik, richtig aufbereitet, doch etwas umfangreich wird. Insbesondere eine Erklärung der Skiplists ist nicht einfach. Sie muss ja verständlich sein. Schaut Euch doch einfach mal die Arbeit von W.Pugh an. Da wird einem doch schwindelig. :dance:

[idealist]

@alzaimar: Danke, Super vergleich.

Oft ist der Schlüssel eindeutig, d.h man Braucht keinen AnsiUpperCase oder AnsiCompareText. Dann ändern sich die Ergebnisse im Bereich bis ca 30.000 Einträge. So wird sortierte Liste bis zu 2,5 schneller als Dictionary (Hashtable) und Dictionary wird schneller als Skiplist.

Wenn es möglich ist, zuerst alle Daten in die Liste zu speichen und danach zu sortieren. Dann geht auch Einfügen in die Liste deutlich schneller als in die Dictionary oder SkipListe.
http://img12.imageshack.us/img12/569...hot017y.th.png

[alzaimar]

Danke für das Kompliment. :stupid:

Natürlich gibt es immer Möglichkeiten, die Datenstrukturen für eigene Bedürfnisse zu optimieren. Allgemeingültig sind sie damit jedoch nicht mehr.
Ein schönes Beispiel hierfür sind Listen, die zuerst befüllt und dann einmalig sortiert werden, um die anschließende Binärsuche zu ermöglichen.

Ich kann mir vorstellen, das alle Strukturen von der Vorgabe profitieren, Schlüssel nicht auf Eindeutigkeit prüfen zu müssen.

[Delphi-Laie]

Zitat:

Zitat von alzaimar

In Anbetracht der häufig gestellten Fragen nach 'Suchen in einer Liste' und Ähnlichem hab ich mal vier Verfahren verglichen:
- Stringlist
- AVL-Baum
- Skiplist
- Hashlist

Das Testprogramm fügt zunächst Werte in die jeweilige Datenstruktur ein und sucht sie anschließend wieder. Beim Einfügen wird sichergestellt, das der Eintrag nicht schon in der Liste ist.

Hallo alzaimar, erst mal mein Kompliment für diese umfangreiche erfolgreiche Visualsierung!

Mal eine ganz dumme Frage, ich verstehe die Datenstrukturen nämlich nur ansatzweise: Gibt es in den Datenstrukturen eine - wie auch immer gestaltete - Ordnung in der Weise, daß man die Elemente als sortiert bezeichnen kann oder die sich wenigstens für eine Sortierung verwenden läßt? So etwas lese ich aus Deinen Sätzen sowohl hier als auch im Delphiform heraus. Auch mein Gefühl sagt mir, daß jede optimierte, rationelle Suche eine Ordnung in der Elementemenge voraussetzt. Daß ich das AVL-Sort dank externer Unterstützung umgesetzt bekam, weißt Du ja anhand meines Sortierkinos. Ich hatte mir interessehalber mal Deine Quelltexte der Skip- und der Hashlist zu Gemüte geführt und dort in erster Sichtung ein Unterprogramm gesucht, das in der Titelzeile (Beschreibung) die Zeichenkette "sort" enthält - leider Fehlanzeige.

Wo, also an welcher Stelle, kann man konkret bei den beiden letzten - vermutlich auch für die Sortierung geeignetsten - Suchalgorithmen die Sortierung "abgreifen" bzw. "gewinnen"?

Danke für Deine Aufmerksamkeit und Geduld!

Gruß

Delphi-Laie

[alzaimar]

Eine Hashmap ist unsortiert. Die Schlüssel werden anhand eines Hash-Wertes gefunden (zumindest fast).
Eine Skiplist ist eine etwas komplexere mehrfach verkettete Liste, bei der die Schlüssel sortiert vorliegen.

Ich glaube, ich habe bei beiden einen Enumerator implementiert, also sowas wie: Gehe zum 1.Element, Hole das nächste Element bis keine mehr da sind...

[Delphi-Laie]

Zitat:

Zitat von alzaimar

Eine Hashmap ist unsortiert. Die Schlüssel werden anhand eines Hash-Wertes gefunden (zumindest fast).
Eine Skiplist ist eine etwas komplexere mehrfach verkettete Liste, bei der die Schlüssel sortiert vorliegen.

Ich glaube, ich habe bei beiden einen Enumerator implementiert, also sowas wie: Gehe zum 1.Element, Hole das nächste Element bis keine mehr da sind...

Vielen Dank!

Natürlich hatte ich mich gestern schon mal dezent über die Datenstrukturen „angeschlaut“ und konnte zumindest bei der Skiplist einen Wissenszuwachs erlangen.

Im Prinzip ist mir jetzt schon klar, wie Deine Algorithmen auch für Sortierungen verwandt werden können. Ich werde mich versuchen. Vielleicht gelingt es mir, mein Sortierkino noch mit 1-2 „Turbo(s)“ zu veredeln.

[p80286]

Könntet Ihr mir bezüglich der Skiplist etwas auf die Sprünge helfen?
Die vorhandenen Beispiele und Erklärungen beschreiben die Skipliste ,Daten + 3..X Zeiger auf Nachfolger , wobei der "größte" Zeiger ,beim ersten Listenelement, direkt auf das letzte zeigt, der "zweitgrößte" 2,3 Elemente überspringt und schließlich der "kleinste" alle Elemente miteinander verbindet. OK da kann man beim Suchen "springen" aber ich seh die Logik in dieser Liste nicht. Bei einem Baum ist es ganz simpel rechts herum ist größer, links herum ist kleiner (gut gleich groß gibt es auch noch). Diesen einfach zu erkennenden Ansatz seh ich bei der Skipliste nicht.

Gruß
K-H

[acadam71]

Mein Test: der AVL Baum benötigt im Testprogramm bei 100.000 Inserts bereits 1 Sekunde. Mein Laptop: Duo Centrino mit 2 GHz.

Ich habe einen AVL Baum selbst programmiert, der schafft in 1 Sekunde aber fas 1 Mio Inserts. Wie kann das sein? Er hat weit weniger Quellcode (357 Zeilen) und benutzt keinen Assembler. Und trotzdem ist er 10 mal so schnell, und das obwohl ich sogar GUIDS (Jeweils 40 Zeichen) einfüge anstatt wie im Testprogramm Integer Werte. Offensichtlich ist der dort benutzte Quellcode nicht gerade optimal, so dass ich davon ausgehe, dass der AVL Baum die beste Datenstruktur ist. Abgesehen davon macht er alle Funktionen wie Insert, Delete, Update und Select(suche) in O(log(n)) und zwar im WORST CASE! So weit mir die Theorie vertraut ist, schafft das keine der anderen Strukturen.

Edit: Mein Quellcode für den AVL ist von Niklaus Wirth, aber auf Objekte angepasst (anstatt Zeiger).

[pertzschc]

Zitat:

Zitat von alzaimar

Insbesondere eine Erklärung der Skiplists ist nicht einfach.

Hallo alzaimar,

ich denke, ich habe einen Fehler entdeckt:

Delphi-Quellcode:

  TcsStringSkipList = Class
...
  Public
..
    Function Find (aKey : String; Var aInfo : Pointer) : Boolean;
    Procedure CurrentData (Var aKey : String; aInfo : Pointer); // aInfo ist nicht als var deklariert
..
    End;

Damit kann man beim Iterieren keinen Pointer zurückbekommen. Beispiel:

Delphi-Quellcode:

      // setze auf 1. satz
      FSDBObjectList.First;
      // schleife bis ende der liste erreicht
      while (not (FSDBObjectList.EndOfList)) do begin
        // nimm aktuellen versicherten
        versicherter := nil;
        aPointer := nil;
        testStr := '';
        FSDBObjectList.CurrentData(testStr, aPointer); // ohne das var ist aPointer immer nil
        if (aPointer <> nil) then begin
          versicherter := TVersicherter(aPointer);
          ..
        end;
        FSDBObjectList.Next;
      end;

mit

Delphi-Quellcode:

..
    Function Find (aKey : String; Var aInfo : Pointer) : Boolean;
    Procedure CurrentData (Var aKey : String; var aInfo : Pointer); // analog zu Find()
..

funktioniert das Ganze.

Liege ich mit meiner Vermutung richtig?
Gruß,
Christoph

[webcss]

Hallo,

hab mal ein bisschen damit gespielt und mal einen Red-Black-Tree mit einbezogen.
Die Ergebnisse sind ernüchternd, der Red-Black Tree outperformt alles andere, auch die vielzitierte SkipList.
Im Anhang mal der verwendete RBTree Code.

Zum Wertevergleich diente TListSortCompare wie folgt

Delphi-Quellcode:

function rbTreeCompare(Item1, Item2: pointer): Integer;
begin
  if Integer(Item1) < Integer(Item2) then
    Result:= -1
  else if Integer(Item1) > Integer(Item2) then
    Result:= 1
  else
    Result:= 0;
end;

[idealist]

Zitat:

Zitat von webcss

Die Ergebnisse sind ernüchternd, der Red-Black Tree outperformt alles andere, auch die vielzitierte SkipList

Hallo webcss,
Sehe ich es richtig, dass bei dir nach Zahlen gesucht wird? Es würde ja die Performance deiner Implementation erklären. In dem Projekt hat man ja Strings verglichen, was natürclich viel mehr Zeit kostet.

[webcss]

Zitat:

Zitat von idealist

Hallo webcss,
Sehe ich es richtig, dass bei dir nach Zahlen gesucht wird? Es würde ja die Performance deiner Implementation erklären. In dem Projekt hat man ja Strings verglichen, was natürclich viel mehr Zeit kostet.

UUPS, das stimmt :oops:

Aber, halt, mal schnell auf String umgesetzt

Delphi-Quellcode:

function rbTreeCompare(Item1, Item2: pointer): Integer;
begin
  Result:= CompareText(string(Item1), string(Item2));
end;

Und das Ergebnis fällt erwatungsgemäß schlechter aus, aber immernoch schneller als die SkipList; ab 140000 Einträgen macht dann das Dictionary das rennen.

Tested against 1.000.000 Entries.

[idealist]

Für den vergleich würde ich AnsiCompareText nehmen, die ist noch ein bischen langsamer, aber die (oder AnsiUpperCase) wir in den anderen algorithmen verwendet. Oder auch Funktionen ohne prefix Ansi in den anderen Algorithmen nehmen.

[webcss]

...und weg war er!

SkipList rocks again!

[idealist]

Zitat:

Zitat von webcss

SkipList rocks again!

Da bin ich eigentlich nicht so sicher.

Delphi-Quellcode:

function TcsStringSkipList.Find(aKey: String; var aInfo: Pointer): Boolean;
var
  k : Integer;
  p,q : PStrNode;

begin
// q := GetStrNode (aKey, fUpdate);
  p := fHeader;
  for k:= flevel downto 1 do begin
    q := p^.ndFwd[k];
    while q^.ndkey < aKey do begin
      p := q;
      q := p^.ndFwd[k];
      end;
    end;
  Result := (q^.ndKey = aKey);
  If Result Then aInfo := q^.ndInfo;
end;

hier soll man auch Ansi konform vergleichen

[webcss]

habs mal mit ansicomparetext getestet:

Das wäre das Ende der SkipList.
Bei 200.000 Einträgen ist Schluss mit Lustig (Suchzeit > 5 Sek.), beim Tree nach 500.000 Einträgen; einzig das Dictionary hält durch bis 1.000.000.

Wohlbemerkt, solange der Key ein string ist.

Nimmt man als key einen Integerwert, so sind AVL, SkipList und RBTree beim Insert in etwa gleich,
beim suchen siegt AVL vor RB und Skiplist.

[idealist]

Zitat:

Zitat von webcss

Nimmt man als key einen Integerwert, so sind AVL, SkipList und RBTree beim Insert in etwa gleich

Das sie AVL, SkipList und RBTree in etwa gleich sind wundert mich nicht. Alle haben für das Suchen gleich Kosten von O(log(n))
Die grösten unterschiede ligen in worst case.

Intressanter sind ThashedStringList und Dictionary. Hier kostet das suchen O(1) in normal fall und O(n) in worst case. Die solln die schnellsten sein. Ich frag mich nur halt was für ein Mist CodeGear gebaut hat?!

Es gibt noch eine Datenstruktur die Konkurenz der Hashtable macht - B*-Bäume. Es wäre intresant diese su implementieren.

[alzaimar]

Bevor man vergleicht, muss man dafür sorgen, das man Apfelsorten untereinander vergleicht, und nicht Äpfel mit Birnen.

Alle Testszenarien stellen sicher, das ein Schlüssel nur 1x eingefügt wird, der Schlüssel also eindeutig ist. Daher muss vor dem Einfügen eine Suche durchgeführt werden.

Berücksichtigt man das, wundert nicht, das RB-Tree und AVL-Tree in etwa identisch hinsichtlich ihres Performanceverhaltens sind. Beide implementieren ausgleichende binäre Bäume.

Und was die Vergleichsroutinen (CompareText, AnsiCompareText usw.) anbelangt, sollte man hier erst dann ein Finetuning betreiben, wenn man sich auf eine Datenstruktur festgelegt hat. Beispielsweise würde ich immer zu einer Skiplist tendieren, wenn ich die Schlüssel sortiert benötige, z.B. um sie aufzulisten.

In allen anderen Fällen verwende ich eine Hashmap (Dictionary), vor allen dingen, wenn ich INTEGER als Schlüssel verwende. Das schreit ja förmlich nach Hashmap (Hash = Key mod Prime).

Allerdings habt ihr auf eine Schwachstelle des Vergleiches hingewiesen: Die TStringlist und der AVL-Baum verwenden die Windows-Funktion 'CompareString', die sehr langsam ist. Ersetzt man diese durch 'CompareStr', die etwa in der Skiplist und im RB-Tree verbaut sind, sind die Unterschiede naturgemäß nicht mehr so groß: In der Tat liegen dann alle Strukturen sehr nahe beieinander.

Mit dieser Modifikation läuft selbst eine TStringlist schnell genug:

Delphi-Quellcode:

type
  TFasterStringList = class(TStringList)
  protected
    function CompareStrings(const S1, S2: string): Integer; override;
  end;

function TFasterStringList.CompareStrings(const S1, S2: string): Integer;
begin
  if CaseSensitive then
    Result := CompareStr(S1, S2)
  else
    Result := CompareText(S1, S2);
end;

Ich habe die Vergleichsfunktionen angepasst, danach ergibt sich ein drastisch verändertes Bild: Die hochgelobte Skiplist verhält sich nun endlich so, wie von vielen Experten prognostiziert: Sie ist beim Suchen längst nicht so schnell wie befürchtet: Also keine Fluxkompensation, kein algorithmischer Tunneleffekt.

Ich prüfe meine Ergebnisse und poste das Resultat in naher Zukunft.

[idealist]

Zitat:

Zitat von alzaimar

Bevor man vergleicht, muss man dafür sorgen, das man Apfelsorten untereinander vergleicht, und nicht Äpfel mit Birnen.

Ganz Genau.

Zitat:

Zitat von alzaimar

Und was die Vergleichsroutinen (CompareText, AnsiCompareText usw.) anbelangt, sollte man hier erst dann ein Finetuning betreiben, wenn man sich auf eine Datenstruktur festgelegt hat.

Ich betrachte es nicht als "Finetuning", sondern als "Äpfel und Birnen". So werden Suchverfahren in Komplexitätstheorie nach Anzahl der Vergleiche in die Komplexitätsklaen aufgeteilt. Es wird dort angenomen, dass der Vergleich zwei Werte in allen Algorithen gleich Kostet. Nähmlich 1 Operation. Es ist sehr wichtig, dass die kosten fürs Vergleichen in allen Algorithmen ungefähr gleich gross sind. (Was bei der Integer vergleich automatisch der Fall war)

Zitat:

Zitat von alzaimar

Die TStringlist und der AVL-Baum verwenden die Windows-Funktion 'CompareString', die sehr langsam ist.

Dictionary werwendet auch AnsiUpperCase (behandelt aber auch regionale Buchtaben, wie auch Windows-Funktion 'CompareString') was deutlich langsamer als UpperCase (diese Funktioniert analog zu CompareText/CompareStr) ist.

[alzaimar]

Hast schon Recht: Das von mir erstellte Testszenario vergleicht wirklich Äpfel mit Birnen. Allerdings habe ich native Delphi-Strukturen mit aufgenommen, um zu zeigen, wer wann wo wie schnell bzw. lahm ist.
Tunen kann ja, wer will. Nur die eh schon schnelle Dictionary wurde durch diese blöden AnsiUppercases (die mir irgendwann reingerutscht sind), unnötig ausgebremst.

Ich poste hier mal eine Version, die -glaube ich- in den einzelnen Units identische Vergleichsoperationen (CompareStr) verwendet.

Geht doch einfach mal über den code und prüft, ob das alles Äpfel sind.