TreeView-Nodes anhand Pfad-String finden (zu langsam)

[Satty67]

Ich baue ein TreeView aus einer Datenquelle auf.
Die daten kommen mit zwei Informationen an: Kategorie und Dateninhalt

Die Kategorie ist wie ein Verzeichnis-Pfad aufgebaut: Kategorie\Subkategorie\Datenbeschreibung (bis Level 8 ) und wird damit passend in ein TreeView einsortiert. Leider kommen die Daten nicht nach Kategorie sortiert an, denn dann könnte ich den TreeView "on the fly" aufbauen.

Ich muss also ständig suchen, welcher Node zum PfadString passt, dort einsortieren oder neu anlegen. Dazu schneide ich den Pfad aus (Bsp. Kategorie\Subkategorie\) und übergebe den an die u.a. Funktion "FindNodeByPath". Je nach Rückgabe lege ich nur den Datennode an oder eben die fehlende Kategorien-Nodes.

Delphi-Quellcode:

(***************************************************************************
  Funktion, die aus einem Node (mit Parents) ein PathStr bildet
  Achtung! aNode-Pointer wird verändert
***************************************************************************)
function GetNodePath(aNode:TTreeNode; WithDelimiter: Boolean): AnsiString;
begin
  if WithDelimiter then Result := aNode.Text +'\'
    else  Result := aNode.Text;

  while assigned(aNode.Parent) do begin
    aNode := aNode.Parent;
    Result := aNode.text + '\' + Result;
  end;
end;

(***************************************************************************
  Finden einen Node durch Angabe des Pfadnamen
  Achtung! aPath-Wert wird verändert
***************************************************************************)
function FindNodeByPath(const aTreeView: TTreeView; aPath: AnsiString): TTreeNode;
var
  i : Integer;
begin
  Result := NIL;
  if Assigned(aTreeView) and (Length(aPath)>0) then begin

    // Pfadstring UpperCase und Delimiter anfügen
    aPath := AnsiUpperCase(aPath);
    if aPath[length(aPath)] <> '\' then aPath := aPath +'\';

    // Alle Items aus dem TreeView testen
    for i := 0 to aTreeView.Items.Count-1 do begin
      // Vergleich, wenn positiv, dann Abbruch der Schleife
      if AnsiUpperCase(GetNodePath(aTreeView.Items[i], True)) = aPath then begin
        Result := aTreeView.Items[i];
        Break;
      end;
    end;

  end;
end;

Das funktioniert auch, wird aber proportional zu Datenmenge immer langsamer. Vor allem weil bei der Methode auch die irrelevanten Daten-Nodes mit geprüft werden.

Kann man das auch schneller lösen?

Meine Ideen bisher:

- Eine StringList parallel nur mit Ordnernamen und Node-Object, die ich dann via IndexOf durchsuche.
- oder Node.Data kennzeichnen, damit ich wenigstens die Daten-Nodes beim Stringvergleich ausklammern kann

Beide Ideen könnte ich selber umsetzen, aber nimmt mir die universelle Eigenschaft von "FindNodeByPath". Deshalb suche ich nach einer Idee, die innerhalb von "GetNodePath" oder "FindNodeByPath" verbessert, ohne jetzt spezielle Vorbereitung der TreeNodes zu fordern.

PS: VirtualTreeView hätte ich mir gerne mal angeschaut, scheint aber nicht für D5 zur Verfügung zu stehen.
PPS: String ist bei D5 noch ein AnsiString

[himitsu]

anstatt zu jedem Node erstmal dessen Pfad zu bestimmen und dann zu vergleichen,

wäre es bestimmt schneller, wenn du den übergebenen Pfad zerlegst und dann diesen stückchenweise suchst.

hätte den Vorteil, daß im schlimmsten Fall nicht der ganze Baum durchsucht werden muß.

und du hättest gleich den ersten bereits existierenden Node-Teil
(am unteren Beispiel die Suche nach b\x\u\q ... man braucht also ab b\x\ anfangen den neuen Node einzubauen ... der Erste Teil exisitert ja schon)

z.B.

Code:

a
  d
    i
      m
  e
    j
b
  f
    
  g
    k
    l
      n
  x
c
  h

wenn man hier z.B. "b\x" möchte suchst du fast den gesamten Tree ab

Code:

zusammen   stückchenweise
a          a
a\d
a\d\i
a\d\i\m
a\e
a\e\j
b          b
b\f        b\f
b\g        b\g
b\g\k
b\g\l
b\g\k\l
b\x        b\x

PS:

Delphi-Quellcode:

  if WithDelimiter then Result := aNode.Text +'\'
    else  Result := aNode.Text +'\';

irgendwie ist Result da immer das Selbe :angel2:

[Satty67]

Also quasi erst Level 0 durchsuchen, dort dann bei passendem Namen weitermachen?
Klingt schonaml sehr gut, werde ich nachher versuchen umzusetzen...

€: Dein Edit verwiirt mich jetzt kurz, das muss ich nochmal ganz langsam lesen. Scheine ich richtig verstanden zu haben... erstmal auf Level 0 bleiben.

Zitat:

Zitat von himitsu

irgendwie ist Result da immer das Selbe :angel2:

Danke, verwende die Funktion auch zum Pfad generieren bei Daten-Node. Wäre da wohl nachher gestolpert (im Moment wurstel ich ja noch am Einlesen).

[himitsu]

Zitat:

Zitat von Satty67

Also quasi erst Level 0 durchsuchen, dort dann bei passendem Namen weitermachen?

Scheine ich richtig verstanden zu haben... erstmal auf Level 0 bleiben.

genau so ^^

den linken Suchvorgang machst du ja jetzt schon
und beim rechten werden praktisch alle Subnodes ignoriert, die eh nicht passen

[Satty67]

So, also ich bin auf eine Hürde gestossen:

Die Nodes kennen Ihre Sub-Nodes nicht. Keine Itemlisten wie z.B. beim MenuItem. Nur die globae Itemliste und eben Parent/HasChildren als einzige Zuordnung.

Ich kann also den passenden LvL-0 Node ermitteln, aber danach die Schleife nicht auf die Sub-Nodes beschränken. Den Vergleich natürlich schon, indem ich auf Parent prüfe. Dadurch durchlaufe ich aber die ItemListe gleich mehrmals komplett (je nach LvL-Tiefe).

Kann sein, das ich einen Denkfehler drin hab', dann bitte nochmal in die richtige Richtung schupsen ;)

***

Dein Ansatz war aber natürlich trotzdem ein richtiger Weg, nur hab' ich jetzt das Pferd von hinten aufgezäumt. Ich ermittel vom Schleifendurchlauf den LvL des gesuchten Nodes, indem ich die \ im Pfad zähle. Erst wenn der LvL passt, dann vergleiche ich jeweils den kompletten Pfad miteinander.

Könnte ich es wie oben beschrieben machen, würde sich bei jedem Fund die Datenmenge im Mittel halbieren, so ist es leider nicht ganz so effektiv. Das hat aber immerhin etwa 30% mehr Geschwindigkeit gebracht:

Delphi-Quellcode:

function FindNodeByPath(const aTreeView: TTreeView; aPath: String): TTreeNode;
var
  i, lvl : Integer;
  NodeText : String;
begin
  Result := NIL;
  if Assigned(aTreeView) and (Length(aPath)>0) then begin

    // Pfadstring UpperCase
    aPath := AnsiUpperCase(aPath);

    // Delimiter anfügen
    if aPath[Length(aPath)] <> '\' then aPath := aPath +'\';

    // Zählen welcher Level der Node haben müsste
    lvl := -1;
    for i := 1 to Length(aPath) do
      if aPath[i]='\' then inc(lvl);

    // Alle Items aus dem TreeView testen
    for i := 0 to aTreeView.Items.Count-1 do begin

      // Vorbedingungen testen
      if (aTreeView.Items[i].Level = lvl)  then begin
        // Jetzt evtl. passenden Node-Pfad mit Gesuchtem vergleichen
        if AnsiUpperCase(GetNodePath(aTreeView.Items[i], True)) = aPath then begin
          Result := aTreeView.Items[i];
          Break;
        end;
      end;

    end;
  end;
end;

"GetNodePath" in die Schleife zu bauen (statt Funktionsaufruf) bringt übrigens keine 100ms. Auch nicht schneller, vorher neben LvL noch Node.Text zu vergleichen (das hatte ich auch schon mit drin).

Im ganzen werden übrigens 24.000 Nodes angelegt. Die erste Methode benötigte dazu noch >30.000ms. Die etwas optimierte nur noch 20.000ms. Die ganz andere Methode mit der String/Object-Liste und IndexOf ist allerdings immer noch um Längen schneller (<3.000ms).

Vielleicht hab' ich ja oben einen Denkfehler gemacht, indem ich himitsu's Vorschlag verworfen hab'. Aber sieht so aus, als ob die spezielle Datenstruktur des TreeView nicht mehr hergibt?

€: Gerade kommt mir etwas in den Sinn. Kommt der Eintrag "Kat\SubKat" immer nach dem Eintrag "Kat" in der ItemListe? Also ganz egal wie oft zuvor Nodes zugefügt und gelöscht worden sind? Wenn ja, müsste ich mir himitsu's Vorschlag nochmal vornehmen ;)

[himitsu]

Zitat:

Die Nodes kennen Ihre Sub-Nodes nicht. Keine Itemlisten wie z.B. beim MenuItem. Nur die globae Itemliste und eben Parent/HasChildren als einzige Zuordnung.

Delphi-Quellcode:

var Node:   TTreeNode;
  NodeList: TTreeNodes;
  i: Integer;

begin
  NodeList := TreeView1.Items;  // alle Items der Ebene 0
  i        := NodeList.Count;   // Anzahl der SubItems
  Node     := NodeList[0];      // erstes Item

  NodeList := Node.Item;        // alle SubItem
  i        := Node.Count        // Anzahl der SubItems
  Node     := Node.Item[0];     // erstes SubItem

[RWarnecke]

Hallo Satty67,

ich habe einen CodeLib-Beitrag geschrieben, wie ich einen TreeView mit eine Datenbank mit zwei Tabellen dynamisch fülle. Vielleicht hilft Dir der Beitrag weiter. Ich habe das ganze mal bis Level 5 ausprobiert und es funktioniert.

Edit: Hier noch der Link aus der DP.

[Satty67]

@himitsu:

NodeList := TreeView1.Items; // alle Items der Ebene 0

gibt alle Items des TreeView, aber beim Rest hast Du natürlich recht. Es steht auch so in der OH von D5. Wieso ich das wiedermal komplett übersehen hab' soll die Tage mein Therapeut klären.

@RWarnecke

Werde ich mir auf jeden Fall anschauen, auch wenn mich jetzt der Ehrgeiz gepackt hat, meinem bisher fabrizierten Mist selber zu beheben. Wenn ich das beim ersten überfliegen richtig sehe (worauf man sich bei mir wohl nicht verlassen kann), vergleichst Du nur Node.Text und brichst beim Ersten auftreten ab. Bei mir kommt Node.Text aber vielfach vor, nur eben in verschiedene Kategorien verteilt.

[RWarnecke]

Zitat:

Zitat von Satty67

@RWarnecke
Werde ich mir auf jeden Fall anschauen, auch wenn mich jetzt der Ehrgeiz gepackt hat, meinem bisher fabrizierten Mist selber zu beheben. Wenn ich das beim ersten überfliegen richtig sehe (worauf man sich bei mir wohl nicht verlassen kann), vergleichst Du nur Node.Text und brichst beim Ersten auftreten ab. Bei mir kommt Node.Text aber vielfach vor, nur eben in verschiedene Kategorien verteilt.

Das ist nicht so schlimm, weil ich mir die ID zum Kategorienamen merke. Ich habe zum Beispeil folgenden Baumaufbau :

Zitat:

Hauptkategorie (ID = 1 / ParentID = 0)
|
|
------ Subkatgeorie (ID = 2 / ParentID = 1)
| |
| |
| ------- Subkategorie (ID = 3 / ParentID = 2)
|
|
------ Subkategorie (ID = 4 / ParentID = 1

Du kannst es ja ausprobieren, ob der Aufbau von Deinem TreeView funktioniert, indem Du Dir das Code-Orakel von mir runterlädst.

[himitsu]

nicht getestet:

Delphi-Quellcode:

Function FindNodeByPath(aTreeView: TTreeView; Const aPath: String): TTreeNode;
  Var Path: Array of String;
    i: Integer;

  Begin
    Result := nil;
    Path   := Explode('\', ExcludeTrailingBackslash(aPath));
    If Path = nil Then Exit;
    Result := aTreeView.Items.GetFirstNode;
    i      := 0;
    While Assigned(Result) do Begin
      If Result.Text = Path[i] Then Begin
        If i < High(Path) Then Begin
          Inc(i);
          Result := Result.getFirstChild;
        End Else Exit;
      End Else Result := Result.getNextSibling;
    End;
  End;