Optimierungsproblem (Tabellen mit Baumstruktur)

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

[Zacherl]

Zitat von 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?

Es trifft nicht auf alle Attribute zu, aber auf die meisten schon Wenn ich beispielsweise OBJ1 einlese:

Code:

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

Dann folge ich zuerst dem 1. Element in FilterA und stoße auf einen Filter vom Typ C. Jetzt weiß der Parser hierdurch implizit, dass das Objekt ein Attribut C haben MUSS und liest es aus dem Bytestream.

Zitat von BUG:

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

Nicht zwingend. A sollte immer das erste Element sein. C und D werden "in einem Rutsch" vom Parser ausgelesen. Deren Reihenfolge kann ich also permutieren. Und B kann ich sogar unabhängig direkt zu Beginn auslesen (sogar noch vor A, da ich erkennen kann, ob der Wert zu B gehören kann oder doch ein A-Attribut sein muss).

[BUG]

Und zwingt dich etwas, für die einzelnen Filter Arrays zu nehmen? z.B. sind die so dicht besetzt, dass sich andere Datenstrukturen nicht wirklich lohnen würden?

[Zacherl]

Zitat von BUG:

Und zwingt dich etwas, für die einzelnen Filter Arrays zu nehmen? z.B. sind die so dicht besetzt, dass sich andere Datenstrukturen nicht wirklich lohnen würden?

Sind schon recht dicht besetzt, ja. Dazu kommt, dass die Arrays später nicht aus Zeigern bestehen, sondern aus 2-Byte großen Words. Glaube nicht, dass da eine alternative Datenstruktur von der Größe her mithalten kann. Lasse mich aber gerne eines Besseren belehren