Problem mit der Sortierung im VST

[Assertor]

Hi DPler,

ich stehe gerade etwas auf dem Schlauch:

Hintergrundinfo:
Ich zeige über ein VST Felder einer Datenbank an. Nun habe ich mich per Profiler auf die Suche nach Performance Problemen gemacht, nachdem mir auffiel das ab ca. 1,5 bis 2,5 Mio Datensätzen das ganze alle paar Sekunden langsam wird. Langsam bedeutet hier: Aussetzer wenn man z.B. den Scrollbalken schnell bewegt - genau in der Zeit, wo das Tree seine Anzahl prüft und verändert.

Die Ursachen waren schnell ausgemacht: Im OnBeforeItemErase für die Colorierung statt Index den AbsoluteIndex verwendet (kniffliger Performance-Killer) und toAutoSort war true. Die dahinterliegende Datenbank erhält alle paar Sekunden neue Einträge, die auch angezeigt werden sollen. Bisher wird in einem Timer geprüft, ob die VST.RootNodeCount <> DB.RecordCount ist und ggf. der RootNodeCount erhöht. Ein Trigger von Seiten der Datenbank (Push) ist leider nicht möglich, da die Einträge auch extern erfasst werden und es nur eine embedded DB (SQLite3) genutzt wird.

Alles technisch kein Problem - und rasend schnell auch bei mehr als 2.5 Mio Einträge.

Frage:
Wie kann ich eine DB-gerechte Sortierung umsetzen, die kein Performance-Killer ist?

Für die Sortierung wird nur das Feld bzw. die Spalte Index zugelassen, da hier auch der PK liegt und das OnCompare schnell geht. Wenn jetzt aber per RootNodeCount oder AddChild() neue Einträge dazukommen wird mit/ohne .BeginUpdate/.EndUpdate die ganze Tree neusortiert.

Wenn ich die Daten z.B. per

Delphi-Quellcode:

vstMainGrid.Sort(vstMainGrid.AddChild(vstMainGrid.RootNode),
  vstMainGrid.Header.SortColumn, vstMainGrid.Header.SortDirection, True);

anfüge, werden diese trotzdem an der falschen Position eingefügt (z.B. großer Index > kleiner Index, neue große Index dann "dahinter").

Ich weiß, viele Lösungen verbieten bei dynamischen Trees und DB-konnektierung von sich aus die Sortierung (devexpress u.a.). Trotzdem finde ich eine Basissortierung (1>n, n>1) schöner.

Ideen?

Gruß Assertor

[generic]

Sort wird nur aufgerufen, wenn du es aufrufst. Bei hinzufügen von Nodes wird es nicht aufgerufen.

[Assertor]

Hi,

Zitat von generic:

Sort wird nur aufgerufen, wenn du es aufrufst. Bei hinzufügen von Nodes wird es nicht aufgerufen.

Natürlich, laß es mich mal umformulieren:

- Wenn toAutoSort verwendet wird, stimmt die Sortierung. Wenn jetzt per AddChild() oder Änderung der RootNodeCount die Anzahl geändert wird, wird durch .EndUpdate eine vollständige Neusortierung (müßte intern ein Mergesort sein) ausgelöst, der sehr lahm ist bei ~ 2 Mio Einträgen
- Mit manuellem Sort für das Einfügen eines einzelnen Childs per AddChild (siehe Sourcebeispiel oben) stimmt die Position des angefügten Eintrags trotz .Sort() nicht

Gruß Assertor

[generic]

2) verwundert mich etwas. Vieleicht ein Fehler in der onCompare Methode?


ggf. selbst die Position suchen und an der richtigen Stellen den Knoten einbinden.
Dann brauchst du überhaupt keine Sortierung vom VST.

[Assertor]

Hi generic,

Danke für Deine Hilfe!

Zitat von generic:

2) verwundert mich etwas. Vieleicht ein Fehler in der onCompare Methode?

ggf. selbst die Position suchen und an der richtigen Stellen den Knoten einbinden.
Dann brauchst du überhaupt keine Sortierung vom VST.

Probiere ich seit heute Abend schon. Also toAutoSort aus, manuelle Sortieren per OnHeaderClick und zusätzlich automatische Positionierung neuer Nodes per .InsertNode.

Das geht zwar, aber die Performance ist nur um den Faktor 5 besser als AutoSort. Ohne .InsertNode bzw. ohne Sortierung kann ich 10 Nodes per .AddChild in 0-16ms hinzufügen, das gleiche mit .InsertNode an amInsertBefore dauert ~300ms bei 1 Mio Nodes, ~ 750ms bei 2.5 Mio Nodes bis zu 3.3 Sekunden bei 5 Mio Nodes. Das ganze ist innerhalb eines .BeginUpdate/.EndUpdate Blocks.

Mit AutoSort dauert das bei Änderung des RootNodeCounts ca. 3.5 Sekunden bei ~ 10 neuen Nodes mit 2.5 Mio Einträgen.

Das würde für automatische UI Aktualisierung ausscheiden, da diese unbedienbar würde (Timer fügt neue DB Einträge alle 2,5-5 Sekunden hinzu). Wie gesagt, ich teste jetzt mit einem sonst leeren Form nur die VST-Funktion - da ist nichts mehr mit DB etc.

Was ich bräuchte, wär ein AddChild welches bei gleicher Performance die optische Position berücksichtigt (ganz oben oder ganz unten hinzufügen). InsertNode ist dafür zu langsam - und vor allen Dingen braucht mehr Zeit je größer der VST.RootNodeCount ist.

Gruß Assertor

[generic]

Ich stell mir die Frage wer soll soviele Eintrag lesen?
Ein Mensch ist für die Menge eher ungeeignet.

Vielleicht solltest du allgemein über die Darstellung nachdenken.
Sprich: zusammenfassen oder den Benutzer die Wahl lassen, was er sehen möchte.
Selektionsmöglichkeiten und/oder Grafiken, wenn es um Messwerte geht.

Niemand schaut sich 2 Mio Daten auf einmal an. Alleine das Durchscrollen durch die Daten würde länger als ein Arbeitstag dauern.

Das mit der Sortierung ist trotzdem merkwürdig. Ich habe im größten VST ca. 500k an Zeilen drin, diese Sortieren ohne Probleme mit manuellen Sort.

[Assertor]

Hi,

Zitat von generic:

Das mit der Sortierung ist trotzdem merkwürdig. Ich habe im größten VST ca. 500k an Zeilen drin, diese Sortieren ohne Probleme mit manuellen Sort.

Ja, in der Größenordnung wird das Problem bei heutigen Rechnern absolut nicht sichtbar. Das entspricht auch meinen Tests.

Zitat von generic:

Ich stell mir die Frage wer soll soviele Eintrag lesen?
Ein Mensch ist für die Menge eher ungeeignet.

Vielleicht solltest du allgemein über die Darstellung nachdenken.
Sprich: zusammenfassen oder den Benutzer die Wahl lassen, was er sehen möchte.
Selektionsmöglichkeiten und/oder Grafiken, wenn es um Messwerte geht.

Niemand schaut sich 2 Mio Daten auf einmal an. Alleine das Durchscrollen durch die Daten würde länger als ein Arbeitstag dauern.

Das ist natürlich richtig. Aber: Ich denke mir, es darf trotzdem nicht bedeuten, daß das Programm langsam bis hin zur Unbedienbarkeit wird.

Ich will praktisch nur eine Sortierung Aufsteigend/Absteigend. Es geht hier um Bestellungen, die Tree zeigt nur ID/Datum und Bezeichnung. Der Rest wird dann aus einer DB gelesen sobald der Benutzer etwas auswählt. Bei hochgerechneten Durchschnittswerten kommt die Anzahl maximal hin...

Ich überlege auch schon die Daten zu gruppieren, die Frage ist nur, wo man sinnvoll ansetzt. Nach Jahren oder der Anzahl (können ja trotzdem zu viele pro Jahr sein). Oder alternativ mit einem Node mit "... (Archiv)" wäre eine Idee.

Es wundert mich nur, daß es vorwärts (unsortiert) auch bei 5 Mio Datensätzen wenige Millisekunden dauert, bis das Tree aktualisiert... Ich will ja lediglich eine Bottom-Top Sortierung.

Gruß Assertor

[Assertor]

Hi,

mal als Nachtrag für die, die es interessiert: Ich habe das "Problem" gelöst. Da war einfach eine viel zu komplizierte Logik im ursprünglichen Ansatz.

Anforderung
Die Anforderung ist eine Sortierung entweder von 1..n oder n..1, die der Benutzer durch Klick auf den Columnheader der ersten Spalte auswählen kann. Die interne Sortierung im VST mit Hilfe von OnCompareNode ist sehr schnell, aber erreicht bei großen Datenmengen schnell ein Performancelimit. Große Datenmengen sind hier DB-gestützte Trees mit 2,5 - 5 Mio Nodes.

Lösung
Da die Werte alle linear sind, braucht man kein Quicksort o.ä., sondern nur eine Neuzuweisung der vorhandenen Zeilennummern. Es wird also statt zu sortieren einfach die hinterlegte Indexnummer geändert bzw. umgekehrt.

Das einzige Problem war die Benutzerauswahl, also die selektierten Nodes. Hier hatte ich verschiedene Ansätze mit Hilfe von Integer-Arrays und Nodelisten getestet. Es stellte sich jedoch heraus, daß diese viel zu langsam sind (wegen des nötigen Vergleichs ob ein Element im Array ist).

Dieses zweite Problem konnte ich lösen, in dem ich die Nodeauswahl mit Hilfe einer Swap Funktion umkehre (also erstes und letzes Element, dann 2. und vorletztes, ... bis zur Hälfte des Trees). Natürlich nur, falls der Auswahlstatus vsSelected bei den Nodes unterschiedlich ist.

Das Hinzufügen der Nodes erfolgt nun im Betrieb per RootNodeCount wenn die Sortierung sdAscending ist und per InsertNode mit amInsertBefore, wenn ein Node vor dem ersten Eintrag benötigt wird (Sortierung sdDescending). Damit die Indexnummer wieder stimmt, wird der Node hier Reinitialisiert und der korrekte Wert zugewiesen.

Zeiten
Ursprüngliche Zeiten:
~3500ms - Sortierung von 2,5 Mio Nodes mit dem VST AutoSort / OnCompareNode
~3500ms - Hinzufügen von 10 Nodes zu dem 2,5 Mio Nodes - Tree (bei genutztem VST AutoSort)

Meine Zeiten:
~94ms - "Sortierung" von 2,5 Mio Nodes (Selection wird dabei auch angepasst und bleibt erhalten)
~0-100ms - Hinzufügen von 10 Nodes zu den 2,5 Mio Nodes (korrekte Nummerierung, davor oder dahinter eingefügt)

Das ganze auf einem langsamen T7xxx Laptop getestet. Selbst bei 25 Mio Nodes sind die Zeiten ok (~ 1,5 Sek).

Also, geht doch

Gruß Assertor

[generic]

[Assertor]

Hi generic,

Zitat von generic:

Danke!

und natürlich

Gruß Assertor