Frage an die Experten für Sortier-Algo-Optimierung

[Codehunter]

Moin!

Ich habe eine Datenbanktabelle mit ca. 1600 Records. Jeder Record hat u.A. eine ID und eine ParentID. Letztere ist ein Verweis auf die ID eines anderen Datensatzes (beides Integer-Werte). Die Daten füttern einen VirtualTreeView. Hier mein bisheriger Code, der zwar ganz exakt das tut was er soll (die Baumstruktur anhand von ID und ParentID bilden), arbeitet aber gaaaanz schröcklich langsam.

Die jetzige Routine arbeitet so, dass zunächst der Baum als flache Liste gefüllt (das geht noch pfeilschnell) und dann über den Sortier-Algo (unterhalb des finally in der Prozedur LoadPlacesTree) die Nodes ihrem jeweiligen Parent "untergeschoben" werden. Das Problem dabei: Innerhalb des Algo laufen zwei verschachtelte Schleifen (Hauptschleife und die in GetPlaceParentNode), sodass im Extremfall 2,56 Mio Durchläufe und Integer-Vergleiche ablaufen.

Idealerweise müsste man den Baum bereits beim Auslesen der Daten aus qryPlacesList aufbauen. Nur kann ich nicht davon ausgehen, dass die Reihenfolge der Datensätze dazu führt, dass jeder ParentNode-Datensatz vor den betreffenden ChildNode-Datensätzen in der Datenmenge liegt. Auch eine Vorsortierung über ein ORDER BY ist nicht möglich, da sich die IDs und ParentIDs aus den Autoinc-Werten bei der Datensatzerstellung bilden und der User später die Sortierung der Nodes frei ändern kann (wobei die IDs erhalten bleiben und sich nur die ParentIDs entsprechend ändern). Es kann also durchaus vorkommen, dass die ParentID größer ist als die ID eines Datensatzes.

Ich wäre euch für Anregungen zur Optimierung sehr dankbar.

Delphi-Quellcode:

type
  PPlaceRec = ^TPlaceRec;
  TPlaceRec = record
    Id: Integer;
    ParentId: Integer;
    Name: string;
    TypeId: Integer;
    TypeName: string;
    AllowedChildTypes: string;
  end;

{...}

function TfrmMain.GetPlaceFromNode(ANode: PVirtualNode): PPlaceRec;
begin
  Result:= tvPlaces.GetNodeData(ANode);
end;

function TfrmMain.GetPlaceParentNode(APlace: PPlaceRec): PVirtualNode;
var
  Node: PVirtualNode;
  Place: PPlaceRec;
begin
  Result:= NIL;
  if APlace^.ParentId = 0 then Exit;

  Node:= tvPlaces.GetFirst;
  while Node <> NIL do begin
    Place:= PlaceFromNode[Node];
    if Place <> NIL then begin
      if Place^.Id = APlace^.ParentId then begin
        Result:= Node;
        Break;
      end;
    end;
    Node:= tvPlaces.GetNext(Node);
  end;
end;

{...}

procedure TfrmMain.LoadPlacesTree;
var
  Node, ParentNode: PVirtualNode;
  Place: PPlaceRec;
begin
  with qryPlacesList do begin
    if not Active then Active:= TRUE;
    if RecordCount > 0 then begin
      First;
      tvPlaces.BeginUpdate;
      try
        while not Eof do begin
          Node:= tvPlaces.AddChild(NIL);
          if Assigned(Node) then begin
            Place:= tvPlaces.GetNodeData(Node);
            if Assigned(Place) then begin
              with Place^ do begin
                Id:= Fields.FieldByName('id').AsInteger;
                ParentId:= Fields.FieldByName('parent_id').AsInteger;
                Name:= Fields.FieldByName('name').AsString;
                TypeId:= Fields.FieldByName('type_id').AsInteger;
                AllowedChildTypes:= Fields.FieldByName('allowed_child_types').AsString;
              end;
            end;
            Next;
          end;
        end;
      finally
        Node:= tvPlaces.GetFirst;
        while Node <> NIL do begin
          Place:= GetPlaceFromNode(Node);
          if Place <> NIL then begin
            ParentNode:= GetPlaceParentNode(Place);
            if Node.Parent = ParentNode then begin
              Node:= tvPlaces.GetNext(Node);
              Continue;
            end;
            if ParentNode <> NIL then begin
              tvPlaces.MoveTo(Node, ParentNode, amAddChildLast, FALSE);
              Node:= tvPlaces.GetNext(ParentNode);
            end else begin
              Node:= tvPlaces.GetNext(Node);
            end;
          end else begin
            Node:= tvPlaces.GetNext(Node);
          end;
        end;
        tvPlaces.FocusedNode:= NIL;
        tvPlaces.EndUpdate;
      end;
    end;
    Active:= FALSE;
  end;
end;

[sx2008]

Hätte die Tabelle das Feld "Level" (0=Root-Knoten, 1=Konten auf nächst tieferer Ebene, ...) dann könnte man nach diesem Feld sortieren.
Ob es sinnvoll ist dieses Feld einzuführen hängt insbesondere davon ab ob der Baum relativ statisch ist; also ob die Knoten ihren Level für immer behalten oder ob "in der Mitte" Konten gelöscht oder eingefügt werden.

[ManBu]

Du könntest bereits gefundene Parents in ein TDictionary stecken und somit das Auffinden des Parents um einiges beschleunigen.

Zumindest reduziert das die Anzahl der Durchläufe.

[Jumpy]

Welche Datenbank steht denn dahinter? Ich weiß z.B., dass es bei Oracle eine Möglichkeit gibt, die Sortierung in der Datenbank machen zu lassen, wobei ich in alten Kram bei uns gucken müsste wie und womit das gemacht wird.

[jfheins]

Der Ansatz von ManBu wird auch hier gezeigt: http://stackoverflow.com/questions/4...flat-structure

Das wäre immerhin schon lineare Laufzeit (also O(n) worst-case) wenn ich mich nicht irre. (Den erstellten Baum am Ende in-order zu durchlaufen ist ebenfalls linear mit der Anzahl der Elemente) Viel schneller (bzgl. big-O) wird es wohl auch nicht gehen.

[DeddyH]

Falls eine Änderung der Tabellenstruktur auch in Frage kommen sollte, sind Nested Sets ggf. einen Blick wert.

[Codehunter]

Ich habe jetzt testweise zum ersten Mal überhaupt mit TDictionary gearbeitet und muss sagen: WHOOOSA!! Das rennt wie die Hölle Den Code jetzt wie folgt umgebaut:

Delphi-Quellcode:

procedure TfrmMain.LoadPlacesTree;
var
  Node, ParentNode: PVirtualNode;
  Place: PPlaceRec;
  Dictionary: TDictionary<Integer, PVirtualNode>;
begin
  with qryPlacesList do begin
    if not Active then Active:= TRUE;
    if RecordCount > 0 then begin
      First;
      tvPlaces.BeginUpdate;
      Dictionary := TDictionary<Integer, PVirtualNode>.Create;
      try
        while not Eof do begin
          Node:= tvPlaces.AddChild(NIL);
          if Assigned(Node) then begin
            Place:= tvPlaces.GetNodeData(Node);
            if Assigned(Place) then begin
              with Place^ do begin
                Id:= Fields.FieldByName('id').AsInteger;
                ParentId:= Fields.FieldByName('parent_id').AsInteger;
                Name:= Fields.FieldByName('name').AsString;
                TypeId:= Fields.FieldByName('type_id').AsInteger;
                AllowedChildTypes:= Fields.FieldByName('allowed_child_types').AsString;

                Dictionary.Add(Id, Node);
              end;
            end;
            Next;
          end;
        end;
      finally
        Node:= tvPlaces.GetFirst;
        while Node <> NIL do begin
          Place:= GetPlaceFromNode(Node);
          if Place <> NIL then begin
            if Dictionary.TryGetValue(Place^.ParentId, ParentNode) then begin
              tvPlaces.MoveTo(Node, ParentNode, amAddChildLast, FALSE);
            end;
          end;
          Node:= tvPlaces.GetNext(Node);
        end;
        Dictionary.Free;
        tvPlaces.FocusedNode:= NIL;
        tvPlaces.EndUpdate;
      end;
    end;
    Active:= FALSE;
  end;
end;

Das Prinzip TDictionary kenne ich ja schon von den assoziativen Arrays bei PHP u.Ä. - dort war ich mit vergleichbaren Algorithmen auch um einiges schneller. Damit ist mir erstmal sehr viel weiter geholfen, VIELEN DANK! Das ist wohl einer der Momente wo man merkt: Man ich war viel zu lange bei Delphi 7 - keine Generics etc. Nützlicher Effekt noch nebenbei: Der Code wurde um einiges kürzer, etliche IFs sind rausgeflogen und lesbarer ist es auch noch ^^

Das gänzlich andere Prinzip "Nested Sets" werde ich mir auf jeden Fall auch anschauen, da ich recht häufig mit derartigen Bäumen zu tun habe. Möglicherweise ergibt sich da ein besseres Anwendungsdesign, mal schauen.

[Blup]

Im Prinzip kann man die Aufgabe, die Knoten vorsortiert zu liefern, auch dem Server aufbürden.

Code:

create procedure P_BAUM_SELECT (
    APARENT_ID integer)
returns (
    ID integer,
    ID_PARENT integer,
    NAME varchar(40),
    TYP integer)
as
begin
  if (aparent_id is null) then
  begin
    /* Aufruf vom Client */
    for select id, id_parent, name, typ
    from       t_baum
    where      (id = id_parent)
    into       :id, :id_parent, :name, :typ
    do begin
      suspend;
      for select id, id_parent, name, typ
      from       p_baum_select(:id)
      into      :id, :id_parent, :name, :typ
      do begin
        suspend;
      end 
    end
  end
  else
  begin
    /* Rekursion */
    for select id, id_parent, name, typ
    from       t_baum
    where      (id_parent = :aparent_id)
    into       :id, :id_parent, :name, :typ
    do begin
      suspend;
      for select id, id_parent, name, typ
      from       p_baum_select(:id)
      into       :id, :id_parent, :name, :typ
      do begin
        suspend;
      end 
    end
  end
end

Wenn die Root-Knoten durch (id_parent is null) gekennzeichnet wären, könte die Abfrage noch etwas schneller sein.