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

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