Vergleich von Suchverfahren mit Beispielen

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