Datenstruktur für Hierarchie/Baum mit Tiefe 3

[dermoritz]

Ich grübele seid Tagen an einer vernünftigen Datenstruktur für eine 3-stufige Hierrchie aus ID->Wert Paaren. Genaugenommen ist es die Hierarchie Bundesländer->Kreise->Gemeinden wobei jedes dieser Dinge eine ID und einen nicht eindeutigen Namen hat. Die ID ist Amtlicher Gemeindeschlüssel ? Wikipedia .

Das ganze ist in einer flachen Tabelle gespeichert und es ist nötig das die komplette Tabelle (mit Hierarchie) auf den Client (ein WebBrowser) geladen wird bzw. eben als Java-Objekt(GWT macht ein JS"Objekt" draus) verfügbar ist. Mein erster Ansatz ist eine Map<String, Map<String,<List<String>>>> also Map<BundeslandID, Map<KreisID,<Liste<GemeindeID>>>>.

Nur fehlen dann die Namen, die könnte ich in einer weiteren Map<Id->Name> halten, aber genau an diesem Punkt kommt mir das alles etwas ineffizient (was den Speicher betrifft) vor. Andererseits in der Map anstelle von String String[2] zu speichern kommt mir auch nicht sehr glorreich vor?!

UseCases sind folgende: gib alle BdLänder/Kreise/Gemeinden, gib alle Kreise zu einem BdLand, gib alle Gemeinden zu einem BdLand, gib alle Gemeinden zu einem Kreis.

Gibt es aus dem Stand eine bessere Lösung für Probleme dieser Art?

Oder könnte ich über eine geschickte (um)Kodierung der IDs mit einer Map auskommen? (die entsprechenden DB-Abfragen basieren alle auf "like" - sie Fragen ob die ID mit z.b. "01" beginnt -> alles was zu Schleswig-Holstein gehört). Damit würde ich bei jedem UseCase immer über alle iterieren aber nur die "benötigten" Einträge Filtern. Wenn das Filtern effizient ist (eine sehr einfach Operation) hätte ich viel Speicher gespart aber nicht sehr viel mehr CPU verbraten?!

 

[maki]

Maps? Pfui... mach dir doch eine inteligentere Datenstruktur draus 😉

Stichwörter zum Googeln: Composite Pattern für die Struktur, Visitor Pattern event. für das traversieren

 

[fastjack]

Stichwort B (*)-Baum vielleicht?

 

[dermoritz]

Danke für die Tips:

zum Kompositum: ich hatte eigentlich gehofft um einen Typ "administrative Einheit" drumrum zukommen bzw. lande ich da immer wieder bei maps.
mein kompositum wäre wie gesagt die "administrative Einheit" sie hätte eine Liste von Kindern (bzs map (id-name)), hätte eine eigene id und einen eigenen namen. Da die gesamte Struktu fest ist würde ein Konstrukteur reichen, der eine ganze Map aufnimmt (die Kinder).
Am Ende hätte ich dann eine ähnliche Struktur die ich vorgeschlagen hab (Map->Map->Map) nur "syntaktisch süßer", oder??
Aber 2 Probleme bleiben bestehen:
1. Ich komme an die Enkelkinder (alle Gemeinden zu einem Bundesland) nur über alle Kreise (for each kreise getKinder) - das ist glaube auch nicht zu vermeiden?!
2. Wie komme ich effizient an einen Namen zu einer ID - ungünstig wäre wenn ich den Baum durchsuchen müsste. Da fällt mir eben bisher auch nix besseres ein, als in einer Map alle Id->Namen zu speichern

zum B(*)-Baum: implementieren würde man den wahrscheinlich auch mit composite pattern?! nur er bietet mir bei weitem zu viel: ich will niemals Elemente löschen oder hinzufügen (nachdem der Baum steht) auch haben meine Knoten nur einen Schlüssel (sich selbst). Und auch hier muss ich über alle Kinder wandern um an die Enkel zu kommen (wie erwähnt kann man das glaube nur mit redundanter Datenhaltung umgehen - 3 Strukturen: BdLand->Kreis, BdLand->Gemeinde, Kreis->Gemeinde)

Um mal meine Frage auf den Punkt zu bringen: Ist die CPU-optimale Lösung für mein Problem mit den 2 Use-Cases, 4 Listen BdLand->Kreis, BdLand->Gemeinde, Kreis->Gemeinde und Id->Name - ist das so?
Gibt es etwas gleich schnelles (mein Ansatz ist glaube O(1)) mit weniger Speicher?
(wie erwähnt wird der Kram letztendlich durch den GWT Compiler in JS übersetzt und landet auf dem Browser - nur was ist besser: viel Speicher oder viel CPU? Crossbrowser-mäßig eher viel Speicher oder? Alte Browser sind ja nicht die schnellsten bei JS?)

 

[fastjack]

Dann schreib Dir eine Datenstruktur, die diese Maps ein wenig kapselt und du von Außen halt einfach darauf zugreifen kannst.

 

[maki]

Moritz, wozu Maps?

Wenn du nach IDs suchen willst ist eine DB wohl besser.

Deine Anforderungen lassen sich Problemlos mit einem Kompositium abdecken.

 

[dermoritz]

@maki natürlich sind die Daten in einer DB nur muss ich sie in den client laden und dort müssen sie in einer Struktur vorligen. und wie ich gesagt habe fumktioniert das mit dem Kompositum wunderbar (also der Tip war gut!).

Nur um mit Kompositums eine Hierarchy aufzubauen muss jedes Kompositum die Liste seiner Kinder kennen.
Also hätte mein Kompositum ein Feld "List<meinKompositum> kinder". Desweiteren hätte jedes Kompositum ein Feld für "name" und ein Feld für "id" (beides Strings).
Darauf könnte ich dann wunderbar meine Methoden (getKinder(meinKompositum), getKindeskinder(meinKompositum)) aufbauen und hätte so eine Kapsleung wie fastjack vorschlägt. Ganz am Ende im Interface brauche ich jedoch immer die Paare id->name (name wird in combobox angezeigt, id ist die referenzs da name nicht eindeutig). Die Rückgabetypen der Methoden könnten dann z.B. List<String[2]> sein oder eben Map<String, String>.

wie gesagt alles wunderbar(falls ich euch richtig verstanden habe) aber 2 Dinge sind eben meiner Meinung nach gleich (oder schlechter) gegenüber meinemAnsatz vom Anfang (Map<String, Map<String,<List<String>>>> ):
1. Um an alle Gemeinden eines Bundeslandes zu kommen muss man über alle Kreise iterieren (die Datenbank bzw. eine redundante Struktur würde das vermeiden).
2. um zu einer gegebenen id den namen zu bekommen (effizient) muss ich in einer "LookUpTable" nachsehen also am besten eine Map<String,String>.
Für letzteres wäre die einfache Struktur mit Kompositum sehr inefizient (iteration über alle Kompositums bis man id findet).

Wie im letzten Post von mir beschrieben: vorläufig kann ich gut mit der cpu-optimalen Lösung arbeiten (die 4 Listen etwas in eine Klasse gekaselt). Nur gebe ich nach wie vor die Hoffnung nicht auf, dass es ein Struktur mit weniger Speicherbedarf (es wird wohl immer O(n) sein aber anstelle von 4*n wäre 3*n oder 2*n eben wünschenswert) aber gleicher Performance(O(1)) gibt (B bäume würden glaube für den 2 use-case O(log n) benötigen?!).

 

[dermoritz]

@maki habe deine "kompositum"-rat befolgt. geht super. nur ist meiner traversierklasse etwas speziell: sie hält alle kompositums in einer flachen Liste. auf die art komme ich an alle ran ohne verschachtelte for schleifen.

 

[maki]

Wenn dir das reicht, dann ist ja gut 🙂

Zur Traversierung von Composites eignet sich übrigens das Visitor Pattern sehr gut, nix verschachtelte Schleifen, sondern Rekursiv 😉
Ist besonders dann zu empfehlen, wenn es keine Änderungen an den Nodes mehr gibt, also weitere Unterklassen bzw. Änderungen an bestehenden.