Optimierungsproblem (Tabellen mit Baumstruktur)

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

[ibp]

Mögliche Herangehensweise:

1. Die Kapazität entspricht dem Widerstand, gibt es mehrere Objekte mit gleichem Widerstand, so wird dieser für diese Objekte mit der Anzahl der Objekte multipliziert

A = 256
B = 3
C = 5
D = 5
E = 4

2. Sortiere die Reihenfolge der Filter nach Widerstand von hoch zu niedrig

Aus...

OBJ1 = {A = 4, B = /, C = 5, D = 3, E = /}
OBJ2 = {A = 54, B = 2, C = 3, D = /, E = /}
OBJ3 = {A = 54, B = 1, C = 1, D = /, E = /}

wird dann...

OBJ1 = {A = 4, C = 5, D = 3, B = /, E = /}
OBJ2 = {A = 54, C = 3, B = 2, D = /, E = /}
OBJ3 = {A = 54, C = 1, B = 1, D = /, E = /}

[Zacherl]

Zitat von jobo:

B=3 & E=4 könnte man z.B. zu X=15 "zusammenfassen"

Das funktioniert leider nicht, da ich später ja immer nur ein Attribut nach dem anderen dekodieren kann. Bei dieser Vorgehensweise bräuchte ich aber ja mindestens schon Zwei

Zitat von ibp:

1. Die Kapazität entspricht dem Widerstand, gibt es mehrere Objekte mit gleichem Widerstand, so wird dieser für diese Objekte mit der Anzahl der Objekte multipliziert
2. Sortiere die Reihenfolge der Filter nach Widerstand von hoch zu niedrig

Das klingt vielversprechend Werde ich die Tage mal versuchen zu implementieren.

[BUG]

Hab ich das richtig verstanden, dass du quasi nur Attribute abfragen kannst, wenn du dir sicher bist, dass das zu untersuchende Objekt das Attribut auch hat?

Also muss im folgenden Beispiel die Reihenfolge A, C, B sein?

Code:

OBJ1 = {A =  1, B = /, C = 1, D = 3, E = /}
OBJ2 = {A = 1, B = 1,  C = 2, D = /, E = /}
OBJ3 = {A = 1, B = 2, C = 3, D = /, E = /}