Optimierungsproblem (Tabellen mit Baumstruktur)

[Zacherl]

Dein zweiter Baum ist nicht ganz korrekt, da OBJ1 ja einen anderen Wert für A hat, als OBJ2 und OBJ3. OBJ1 kannst du in der Betrachtung aber auch vorerst mal ausblenden, da das Problem in meinem Beispiel vorerst nur den Ast A = 54 betrifft.

Der dritte Baum ist prinzipiell korrekt (da ist nur die 004 etwas verrutscht ). Tatsächlich hat jeder Filter in meiner Implementation ein 0-Element, worin ich dann die Objekte einordne, für die der Filter nicht zutrifft. Das Problem ist allerdings nicht, die "unnötigen" Filter loszuwerden (das macht mein Algorithmus schon beim Einfügen neuer Objekte), sondern es geht konkret um die Reihenfolge der notwendigen Filter pro Ast.

Ziel soll sein, die Gesamtkapazität des Baumes zu minimieren.

Hierbei ist zu beachten, dass z.b. ein Filter C, bei dem nur ein Element gesetzt ist, trotzdem die volle Kapazität von 5 besitzt. In meinem Beispiel sieht man im 054er Ast ja ganz schön, dass beim naiven Einfügen (erst FilterA, dann FilterB wenn vorhanden, dann FilterC wenn vorhanden, ..) 1x FilterB und 2x FilterC benötigt werden. Man könnte die Objekte aber genauso gut einordnen, indem man erst 1x FilterC und danach 2x FilterB verwendet. Dadurch, dass FilterB aber eine kleinere Kapazität hat, als FilterC, spart man sich am Ende 2 unnötige leere Plätze.

[Namenloser]

Ok, sorry, dann verstehe ich nicht, was du vorhast. Vielleicht solltest du mal erklären, was du mit "Kapazität" überhaupt meinst und was die Zahlen im Baum bedeuten. Was macht ein Filter überhaupt und wie wird bestimmt wie oft man einen bestimmten Filter braucht? Was sind da die Rahmenbedingungen?

Mit den gegebenen Informationen würde ich sagen, die Gesamtkapazität des Baumes zu minimieren ist einfach: Einfach keinen Filter verwenden

[Zacherl]

Das mit den Kapazitäten hatte ich im ersten Post erwähnt, aber vielleicht nicht gut genug beschrieben. Denk mal kurz nicht an den Baum, sondern nimm die Filter als 1-dimensionale Tabellen (das sind sie in der Implementierung tatsächlich). Attribut A beispielsweise ist ein Byte. Der dazugehörige FilterA ist ein statisches Array mit 256 Elementen. Attribut B ist ein Enum mit 3 Werten. FilterB ist demnach ein statisches Array mit ebenfalls 3 Elementen, und so weiter ..

Als Kapazität bezeichne ich die maximale Anzahl an Elementen pro Filter. Also sozusagen Lenght(FilterArray) .

Die Zahlen im Baum repräsentieren den Index des Elements (weiterer Filter oder Objekt) im jeweiligen Filter Array.

Leider habe ich keinen Einfluss darauf, ob ein Objekt einen bestimmten Filter benötigt, da mein Datensatz vorgegeben ist. Zur Häufigkeit habe ich bisher auch keine Analyse gemacht, aber im Grunde genommen ist die Verteilung auch nicht wirklich relevant, wie ich das sehe.

[BUG]

Mir stellt sich ein bisschen die Frage, warum du (nicht dicht besetzte) Arrays als Filterstufe nehmen willst. Spricht etwas dagegen ein Tupel aus allen Eigenschaften zu hashen oder einen normalen Suchbaum zu verwenden?

Benutzt du für alle Teilbäume die gleiche Filterreihenfolge? Dann sucht du ja quasi eine Permutation der Filter, so das du für deine Objekte einen möglichst kleinen Baum bekommst. Mein Lieblingsansatzfür große Suchräume ist Branch-and-Bound: mit einer Heuristik findest du einen ersten Vorschlag und verfolgst nur Pfade weiter, die noch ein besseres Ergebnis liefern könnten.

Vom Bauchgefühl wäre es gut, für die ersten Stufen große Filter zu nehmen, die möglichst viele Objekte trennen. Dagegen sollten Filter vermieden werden, die Objekte mit gleichen Eigenschaften aber dort unterschiedlichen Werten trennen, insbesondere wenn deren Filter groß sind.

[Zacherl]

Zitat von BUG:

Mir stellt sich ein bisschen die Frage, warum du (nicht dicht besetzte) Arrays als Filterstufe nehmen willst. Spricht etwas dagegen ein Tupel aus allen Eigenschaften zu hashen?

Meine momentane Vorgehensweise ist nach sorgfältiger Prüfung wirklich die einzig Mögliche.

Dein Vorschlag funktioniert aus folgendem Grund nicht:
Der fertige Filter ist eine Art Schablone zum Parsen von wieder anderen Daten. Diese Daten liegen aber in einem Format vor, bei dem ich nicht direkt zu Anfang alle Attribute auslesen kann. Die Art und Weise der Dekodierung hängt zum Einen von der Existenz eines Filters ab, zum Anderen aber auch teilweise von der konkreten Position im Filter.

Zitat von BUG:

Benutzt du für alle Teilbäume die gleiche Filterreihenfolge?

Ja, das ist momentan der Fall. Für die Größe der Struktur ist das aber nicht optimal.

Zitat von BUG:

Vom Bauchgefühl wäre es gut, für die ersten Stufen große Filter zu nehmen, die möglichst viele Objekte trennen. Dagegen sollten Filter vermieden werden, die Objekte mit gleichen Eigenschaften aber dort unterschiedlichen Werten trennen, insbesondere wenn deren Filter groß sind.

Die Filterreihenfolge habe ich bereits mal per Hand auf Basis meiner realen Daten geändert und somit auch schon ein wenig optimieren können. Im Grunde könnte ich es hierbei belassen, aber irgendwie würde mich schon interessieren, was das die minimale Größe ist, wenn ich alle Äste einzeln permutiere.

[jobo]

Ich muss auch mal ein paar doofe Fragen stellen. Bei "Tabellen" bin ich natürlich "hellhörig" geworden, nun geht es gar nicht um SQL, ab nun. Das quasi mal als Entschuldigung, für meine Fragen und Gedanken.
Ich hab Schwierigkeiten mit dem Begriff Kapazität. Und warum will man sie veringern?
In einem Baum würde ich versuchen mit möglichst wenig Knoten, möglichst viele Elemente zu verwalten. Das geht für mich nicht übernander mit den Kapazitäten.
Wodurch ist die "Kapazität" von B - E definiert? Sind das die Werte der Attribute?
Ist die tatsächliche Anzahl der Objekte hinter der Kombination von A-E nicht relevant?

Ein Optimierungsansatz scheint mir trotz meines Unverständnis darin zu liegen, für B-E Metaattribute zu definieren, die entsprechend einer tatsächlichen Häufung oder Nichtexistenz von Kombinationen (oder auch der Objektmenge dahinter) eine "kompaktere" Abbildung (Filterung) erlauben. Die Metaattribute müssen dann natürlich am Ende wieder rückgeführt werden (der Zusatzaufwand für Meta und Zurück) muss natürlich geringer sein, als der Status Quo.

[Zacherl]

Zitat von jobo:

Ich muss auch mal ein paar doofe Fragen stellen. Bei "Tabellen" bin ich natürlich "hellhörig" geworden, nun geht es gar nicht um SQL

Mein Fehler. Hätte von Anfang an besser den Begriff Array statt Tabelle verwendet (denkt man natürlich in dem Moment nicht dran, dass andere Leute Tabelle mit Datenbanken assoziieren werden).

Zitat von jobo:

Ich hab Schwierigkeiten mit dem Begriff Kapazität. Und warum will man sie veringern?

Da die Struktur am Ende ziemlich groß ist, versuche ich die Datengröße zu verringern.

Zitat von jobo:

In einem Baum würde ich versuchen mit möglichst wenig Knoten, möglichst viele Elemente zu verwalten. Das geht für mich nicht übernander mit den Kapazitäten.

Da hast du Recht, allerdings gibt es in meinem speziellen Fall leider einige leere Knoten, die ich nicht ganz vermeiden kann. Ich kann höchstens deren Anzahl optimieren und das ist genau das, was ich letztendlich versuche.

Zitat von jobo:

Wodurch ist die "Kapazität" von B - E definiert? Sind das die Werte der Attribute?

Die Werte der Attribute geben den Index im Array wieder. D ist z.b. ein Enum mit 5 Elementen, demnach ist die Kapazität des entsprechenden Filters auch 5.

Zitat von jobo:

Ist die tatsächliche Anzahl der Objekte hinter der Kombination von A-E nicht relevant?

Bin ich mir nicht ganz sicher, aber wenn ich wirklich jeden einzelnen Ast rekursiv optimiere, sollte das keine Rolle spielen.

Zitat von jobo:

Ein Optimierungsansatz scheint mir trotz meines Unverständnis darin zu liegen, für B-E Metaattribute zu definieren, die entsprechend einer tatsächlichen Häufung oder Nichtexistenz von Kombinationen (oder auch der Objektmenge dahinter) eine "kompaktere" Abbildung (Filterung) erlauben. Die Metaattribute müssen dann natürlich am Ende wieder rückgeführt werden (der Zusatzaufwand für Meta und Zurück) muss natürlich geringer sein, als der Status Quo.

Bin mir nicht sicher, ob ich das komplett verstanden habe. Kannst du mir da eventuell ein Beispiel geben?