Bevor ich am Ende kompletten Unsinn implementiere, möchte ich hier eine kurze Diskussion starten. Vielleicht übersehe ich ja was offensichtliches, oder ggf. einen eleganteren Weg.

Gegeben ist eine Menge A von Objekten, die ich anhand bestimmter Kriterien in kleinere Teilmengen kategorisieren will. Das ganze auch auf zwei oder ggf. ein paar mehr Ebenen. D.h. ich habe im Grunde einen Baum, in dessen Blättern Teilmengen von A zu finden sind.

Die Menge A enthält üblicherweise mehrere 10.000 Objekte, an den Blättern sollen am Ende ein "paar" Objekte enthalten sein. Je nach Wahl der Kriterien oft nur ein einziges, in der Regel jedoch 10-20, selten aber auch mehr. D.h. mein Baum hat eine geringe Höhe, aber unter Umständen einen sehr hohen inneren Knotengrad (1000 und mehr). Viele Knoten können aber auch eine sehr kleinen Knotengrad haben, 1 oder 2 kommt auch häufig vor.

Die Kriterien, nach denen ich aufteile, lassen sich gut als String darstellen. Das schreit förmlich nach einem TDictionary zur Verwaltung der Nachfahren eines Knoten, wobei der Value-Typ eine Klasse ist, die eine TList für Objekte aus A enthält, und wieder ein Dictionary für die weitere Feinaufteilung bzw. Verwaltung der "Enkel". Damit kann ich dann auch ohne vorherige Sortierung der Menge A in Linearzeit mehrere solcher Kategorisierungs-Strukturen parallel aufbauen. (Also einen kleinen Wald mit vielleicht 3 oder 4 Bäumen.)

Nach der Aufteilung brauche ich aber eine Sortierung. D.h. ich möchte z.B. alle Nachfahren eines Knoten sortiert ausgeben, und danach gruppiert auch die Elemente aus A in den Blättern. Die Sortierung kann dabei dem Key (aus dem Dictionary) entsprechen, kann aber auch z.B. nach der Anzahl der Elemente in diesem Teilbaum gehen. Dafür ist ein Dictionary ja nicht ausgelegt. D.h. dafür müsste ich im Anschluss der Aufbauphase das TDictionary in eine Liste umbauen, die dann sortiert und passend ausgegeben wird. Oder anders, ich muss Dictionary und Liste gleichzeitig aufbauen, und das Dictionary beim Einfügen neuer Objekte nur für den Test auf "ist der Key schon vorhanden?" nutzen.

Zusätzlich würde ich beim Aufbau der Struktur (um ggf. Overhead kleinzuhalten) zu Beginn nur mit der Liste zur Verwaltung der Nachfahren starten. Und erst, wenn die Anzahl der verschiedenen Keys eine Schwelle überschreitet (z.B. 5?) auf das Dictionary umschwenken, damit das Einfügen in O(1) bleibt.

Hört sich das sinnvoll an, oder denke ich da viel zu kompliziert?

Moin 😊
Eventuell kannst du dich ja vom sorted dictionary inspirieren lassen: docs.microsoft.com/e...onary-2?view=net-5.0

Wobei das natürlich nix hilft, wenn die Sortierung nicht nach key geht.
Falls es pro Knoten nur eine Sortierung gibt, würde ich eine sortierte Liste und ein Dictionary gleichzeitig halten. (kann man ja in eine Klasse zusammen werfen)
Die Elemente können dann sortiert oder mit key schnell abgerufen werden. Und man kann jederzeit umsortieren 😉

Du kannst auch mal gucken, wie lange die Sortierung braucht. Ggf reicht ja auch das dict und beim sortierten Abruf machst du dann einfach schnell die Sortierung:

Mit 1000 Elementen sollte das ja schnell gehen

Hi,
danke für die Antwort!

jfheins hat folgendes geschrieben :

Falls es pro Knoten nur eine Sortierung gibt, würde ich eine sortierte Liste und ein Dictionary gleichzeitig halten. (kann man ja in eine Klasse zusammen werfen)

Ja, genau das ist auch mein aktueller Ansatz. Eine Klasse, die Liste und Dictionary kapselt. Dabei versuche ich es erst mit "nur Liste", und wenn diese beim Einfügen zu lang wird, erstelle ich zusätzlich das Dictionary, um die doppelte Datenverwaltung bei (vermutlich häufig vorkommenden) kleinen Sammlungen zu vermeiden, und sie nur dann zu verwenden, wenn es sich lohnt.

Ich denke auch, dass das gar nicht anders geht. Schnell ein Element per Key finden, und gleichzeitig nach einem beliebigen Kriterium sortieren ... irgendwo muss man da zusätzlich Speicherplatz verwenden.

jfheins hat folgendes geschrieben :

Eventuell kannst du dich ja vom sorted dictionary inspirieren lassen

So beim Überfliegen der Doku hilft mir das für die Implementierung in Delphi nicht direkt. Ich bin mir auch nicht sicher, welche Datenstruktur da zu Grunde liegt.
Wenn ich mir aber so die Laufzeiten bei den einzelnen Methoden anschaue, dann tippe ich auf eine Skiplist anstelle der Hashmap beim Delphi-Dictionary. Und wenn ich das dann google, lande ich dort: www.delphipraxis.net/45569-skiplist.html

Muss ich mal schauen, ob man das anpassen kann für String-Keys, und ob sich das am Ende für mich lohnen könnte. So auf den ersten Blick aber eher nicht ... zwar habe ich da keine doppelte Verwaltung meiner Datenobjekte, dafür aber an jedem Objekt 8 Links zu anderen Objekten. D.h. die schnelle Laufzeit beim Einfügen/Löschen/Suchen in dem sortierten(!) Konstrukt erkauft man sich durch mehr Speicherplatz. Da meine Anwendung relativ statisch ist (d.h. es gibt nur selten Änderungen, die dann auch nicht so zeitkritisch sind), wäre das vermutlich nicht so sinnvoll. Da ist dann die Kombi aus Hashmap/Dictionary und (gelegentlich) zu sortierende Liste ein guter Kompromiss.