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?
We are, we were and will not be.