Vergleich von Suchverfahren mit Beispielen

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