Optimierungsproblem (Tabellen mit Baumstruktur)

[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?

[jobo]

Zitat von Zacherl:

Zitat von jobo:

"Tabellen" oder SQL

Mein Fehler. Hätte von Anfang an besser den Begriff Array statt Tabelle verwendet

Ach das kann man genauso umgekehrt sehen. Ohne das Stichwort hätte ich das vielleicht gar nicht gelesen.

Zitat von Zacherl:

Zitat von jobo:

In einem Baum würde ich versuchen mit möglichst wenig Knoten, möglichst viele Elemente zu verwalten.

Da hast du Recht, allerdings gibt es in meinem speziellen Fall leider einige leere Knoten, die ich nicht ganz vermeiden kann.

Einige leere Knoten sind doch sicher kein "Engpass"? Sind es vielleicht eher sehr viele?

Zitat von Zacherl:

Zitat von jobo:

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

D ist z.b. ein Enum mit 5 Elementen, demnach ist die Kapazität des entsprechenden Filters auch 5.

Gut, so hab ich mir das vorgestellt.

Zitat von Zacherl:

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.

Wenn ich das richtig verstanden habe, geht es doch wahrscheinlich um Suchgeschwindigkeitsoptimierung und die würde man über eine möglichst gute Gleichverteilung erreichen?

Zitat von Zacherl:

Zitat von jobo:

Ein Optimierungsansatz ..

Kannst du mir da eventuell ein Beispiel geben?

Kann ich leider nicht, ich habe schon ewig nichts mehr mit Bäumen gemacht.
Anhand Deines Beispiels stelle ich mir ein Mapping vor
B=3 & E=4 könnte man z.B. zu X=15 "zusammenfassen", wenn es ein vollständiges Mapping sein müsste-was dann wieder weniger Sinn macht.
X1= B1 E0
X2= B2 E0
X3= B3 E0
X4= B1 E1
X5= B2 E1
X6= B3 E1
X7= B1 E2
X8= B2 E2
X9= B3 E2
X10= B1 E3
X11= B2 E3
X12= B3 E3
X13= B1 E4
X14= B2 E4
X15= B3 E4
Wenn einige Kombis nicht auftreten, wäre B=3 & E=4 dann vielleicht "nur noch" X=9. Analog dann für die weiteren Attribute bzw. in einer anderen Kombination, die "günstiger" ist.

Ob das Sinn macht, hängt dann von der Attributverteilung der Objekte ab. (Und davon, ob ich das Problem überhaupt verstanden habe)