Optimierungsproblem (Tabellen mit Baumstruktur)

[Zacherl]

Hallo zusammen,

ich habe eine Menge von Objekten, welche alle die Eigenschaft A besitzen. Zudem kann jedes Objekt optional noch die Eigenschaften B, C, D und E definieren. Alle diese Eigenschaften geben den Index in einer dazugehörigen Filter-Tabelle an.

Die Filter-Tabellen haben unterschiedliche Kapazitäten:

Code:

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

Aus diesen Filter Tabellen baue ich mir nun einen Baum. Kleines Beispiel:

Code:

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 = /}

FilterA
   | - 001
   | - 002
   | - 003
   | - 0004 = FilterC
   |             | - 1
   |             | - 2
   |             | - 3
   |             | - 4
   |             | - 5 = FilterD
   |                        | - 1
   |                        | - 2
   |                        | - 4 = OBJ1
   |                        | - 3
   |                        | ...
   | - 005
   | ...
   | - 053
   | - 054 = FilterB
   |            | - 1 = FilterC
   |            |          | - 1 = OBJ3
   |            |          | ...
   |            |          | - 5
   |            | - 2 = FilterC
   |            |          | - 1
   |            |          | - 2
   |            |          | - 3 = OBJ2
   |            |          | - 4
   |            |          | - 5
   |            | - 3
   | - 055
   | ...

Und hier sieht man bereits das Problem. Bisher ist die Reihenfolge der Filter Tabellen statisch von A nach E festgelegt. Im Falle von OBJ2 und OBJ3 benötige ich deshalb 1x FilterB (Kapazität 3) und 2x FilterC (Kapazität 5), womit ich auf eine Gesamtkapazität von 13 komme. Hätte ich die Tabellen aber anders angeordnet; sprich zuerst C und dann B, würde ich für diesen Ast 1x FilterC (Kapazität 5) und 2x FilterB (Kapazität 3) benötigen, was eine Gesamtkapazität von 11 zur Folge hätte.

:arrow: Wie würdet ihr an dieses Problem rangehen, um für jeden Einzel-Ast (und somit letztlich auch für den kompletten Baum) die jeweils optimale Konfiguration zu ermitteln?
:arrow: Gibt es eventuell schon effiziente Alogrithmen, die ich für meine Zwecke umbauen könnte (generell wird es wohl auf Bruteforce/Backtracking hinauslaufen, nehme ich an)?

Viele Grüße
Zacherl

[Namenloser]

Bin mir nicht sicher, ob ich es ganz richtig verstanden habe, aber ich versuche es mal in eigenen Worten wiederzugeben:

Code:

FilterA
   | - 0004 = FilterC
   |            | - 5 = FilterD
   |                       | - 4 = OBJ1
   | - 054 = FilterB
   |            | - 1 = FilterC
   |            |          | - 1 = OBJ3
   |            | - 2 = FilterC
   |            |          | - 3 = OBJ2

Das Problem bei der gezeigten Anordnung ist, dass da einmal FilterC direkt unter /FilterA auftaucht und einmal unter /FilterA/FilterB, was unnötig kompliziert ist, weil man es auch so gliedern könnte:

Code:

FilterA
   | - 0004- FilterC
   |            | - 1 = FilterB
   |                       | - 1 = OBJ 3
   |                       | - 2 = OBJ 2
   |            | - 5 = FilterD
   |                       | - 4 = OBJ1

Verstehe ich das richtig?

Also um noch mal zum ersten Baum zurückzukommen, eigentlich steht da ja implizit:

Code:

FilterA
   | - nicht Filter B
   |            | - 0004 = FilterC
   |            |            | - 5 = FilterD
   |            |                       | - 4 = OBJ1
   | - 054 = FilterB
   |            | - 1 = FilterC
   |            |          | - 1 = OBJ3
   |            | - 2 = FilterC
   |            |          | - 3 = OBJ2

Du hast bloß das "nicht Filter B" gleich weggelassen. Aber wenn ich mir das so hingeschrieben mal ansehe und die Kapazitäten mal ignoriere, dann erinnert mich das stark an das Problem der Minimierung von Schaltungen. Dieses "(Filter B) oder (nicht Filter B)" wäre genau so ein Block, denn man z.B. im KV-Diagramm finden und wegoptimieren würde. Für die algorithmische Umsetzung eignen sich natürlich andere Verfahren wie Quine-McCluskey besser. Dein Problem ist leider wohl NP-vollständig.

[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 :stupid:). 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.

:arrow: 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

Delphi-Quellcode:

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:

Zitat von BUG (Beitrag 1335617)

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:

Zitat von BUG (Beitrag 1335617)

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:

Zitat von BUG (Beitrag 1335617)

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:

Zitat von jobo (Beitrag 1335623)

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:

Zitat von jobo (Beitrag 1335623)

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:

Zitat von jobo (Beitrag 1335623)

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:

Zitat von jobo (Beitrag 1335623)

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:

Zitat von jobo (Beitrag 1335623)

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:

Zitat von jobo (Beitrag 1335623)

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:

Zitat von Zacherl (Beitrag 1335645)

Zitat:

Zitat von jobo (Beitrag 1335623)

"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:

Zitat von Zacherl (Beitrag 1335645)

Zitat:

Zitat von jobo (Beitrag 1335623)

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:

Zitat von Zacherl (Beitrag 1335645)

Zitat:

Zitat von jobo (Beitrag 1335623)

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:

Zitat von Zacherl (Beitrag 1335645)

Zitat:

Zitat von jobo (Beitrag 1335623)

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:

Zitat von Zacherl (Beitrag 1335645)

Zitat:

Zitat von jobo (Beitrag 1335623)

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)