[solved] Größe eines multidimensionalen Arrays ändern

[B.G.Michi]

Guten Abend

Ich bräuchte mal wieder eure kompetente Meinung:
es geht um die Templateklasse für eine multidimensionales Array (Dimension als Templateparameter). Das funktioniert soweit auch ganz gut, allerdings hakt es an einer Stelle, und zwar beim ändern der Größe. Es soll nicht bei jedem ändern der Größe neuer Speicher allokiert werden, sondern, wenn der bereits allokierte Speicher für die neue Größe des Arrays ausreicht, dieser Speicher weiterverwendet werden.

Dabei soll das Objekt mit den "Koordinaten" x1, x2, ..., x_n an der Stelle (((xn * size.x_n-1 + x_n-1) * size.x_n-2 + x_n-2) * ...) * size.x1 + x1 im Array liegen, also einfach nach Zeilen, Ebenen, ... geordnet, oder anderst: es soll immer der komplette vordere Teil des allokierten Speichers verwendet werden (ist klar was ich damit meine?). Das bedeutet, dass beim Ändern der Größe des Arrays, Objekte darin verschoben werden müssen (move assignment) und da wird es kompliziert. Für reines vergrößern oder verkleinern ist das relativ einfach, es gibt nur Probleme, wenn das Array in manchen Dimensionen vergrößert und in anderen verkleinert wird.

In welcher Reihenfolge muss ich den Array durchlaufen und die Objekte verschieben, damit ich nicht per "a = move(b)" noch mit Objekten belegte Speicherstellen überschreibe?
Ist es überhaupt (mit akzeptablem Aufwand) möglich das zu bewerkstelligen, ohne Objekte doppelt zu verschieben?

auf jeden Fall schon mal vielen Dank
JFF_B.G.Michi

[eXile]

Magst du mir mal ein Bild dazu malen (d.h. für zwei Dimensionen)? Ich glaube nicht, dass ich dein Problem hinreichend erfasst habe.

[B.G.Michi]

hier einmal für die Größenänderung eines 2-dimensionalen Arrays von (x = 3, y = 2) nach (x = 2, y = 2)
man sieht die einträge an den Positionen 3 und 4 im Speicher müssen nach 2 bzw. 3 geschrieben werden.

[ftb]

Ich versteh das Problem nicht so recht. Du kannst doch einfach ein eindimensionales Array verwenden und für das den Speicher allokieren und dann entsprechend herum schieben und entsprechende Operatoren/Zugriffsfunktionen schreiben.

[Stephan Theisgen]

Machen wir ein Beispiel-Array

a1 a2 a3 a5 ------------> a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4
b1 b2 b3 b4
c1 c2 c3 c4

Fall 1: Beide Dimensionen verringern:

Dann streichst Du zunächst die Zeile c, dass ist einfach...
dann nimmst Du dir jeden noch übrigen Dreierblock (außer dem ersten) und schiebst in eins nach vorne, also b1, b2, b3

ergibt also:

a1 a2 a3 ------------> a1 a2 a3 b1 b2 b3 (b3 b4 c1 c2 c3 c4)
b1 b2 b3

Fall 2: Beide Dimensionen vergrößern:

Dann nimmst Du einfach jeden Block und zerrst ihn entsprechen auseinander, aber immer von hinten anfangen, sonst überschreibst Du:

a1 a2 a3 a4 a5 ------------> a1 a2 a3 a4 (b1) b1 b2 b3 b4 (c2) c1 c2 c3 c4 (xx xx xx xx xx xx)
b1 b2 b3 b4 b5
c1 c2 c3 c4 c5
d1 d2 d3 d4 d5

Fall 3: Breite verringern, Höhe erhöhen

Ganz einfach wie in Fall 1 die Blöcke zusammen schieben, aber am Ende einfach eine neue Zeile hinzufügen

a1 a2 a3 ------------> a1 a2 a3 b1 b2 b3 c1 c2 c3 (c2 c3 c4)
b1 b2 b3
c1 c2 c3
d1 d2 d3

Fall 4 Breite erhöhen, Höhe erniedrigen

Das ist nicht ganz so einfach. Du löschst erstmal die letzte Zeile (soweit der Speicherplatz nicht benötigt wird) und
schiebst dann alle verbleibenden Blöcke von hinten auseinander

a1 a2 a3 a4 a5 ------------> a1 a2 a3 a4 (b1) b1 b2 b3 b4 (c2)
b1 b2 b3 b4 b5

Als Hilfe: die neue Größe lässt sich immer einfach im Vorhinein berechnen... Dann einfach die übrigen Blöcke auseinander ziehen
und das dann von hinten anfangen, bzw. beim verkleinern zusammenziehen, dass dann immer von vorne. Außerdem gilt Zeile einfügen und löschen
ist ganz einfach, um die Spalten mußt Du Dir dann jeweils Gedanken machen.

Ich hoffe das hat etwas weiter geholfen..
Gruß Stephan

[B.G.Michi]

@Stephan Theisgen:
ja genau das suche ich, für 1-dimensionale Arrays ist das sowieso trivial, für 2-dimensionale funktioniert es genau so wie du geschrieben hast, aber schon für 3-dimensionale Arrays wird es kompliziert, und auch 4-dimensionale Arrays könnte man mal brauchen (z.B. für einen 3D-Texture-Array). ich suche also die n-dimensionale Verallgemeinerung...
(wobei ich mir wie schon geschrieben auch nicht mal sicher bin ob das überhaupt vernünftig funktioniert)

[Stephan Theisgen]

Ah, so langsam verstehe ich das Problem. Nur als Schnellschuß: Könnte schon funktionieren... Es klappt für n = 1 und n = 2, da sollte sich eine Indutkion für eine Verallgemeinerung auf beliebige n ergeben... Aber wie die konkret aussieht, dass ist nicht einfach!

Nachtrag:
Wie wäre es mit einem einfachen Mapping? Du kennst die alten Koordinaten und die neuen, einfach die Werte an den alten Koordinaten bei einer Vergrößerung von hinten auslesen und auf die neuen kopieren, bei einer Verkleinierung das ganze natürlich von vorne beginnen. Das sollte funktionieren. Was ich jetzt aber nicht garantieren kann ist, dass da auch keine Werte überschrieben werden.

[B.G.Michi]

das dürfte wohl nicht funktionieren, da bei ungünstigen Größenänderungen nicht alle "Pfeile" in meiner Zeichnung oben in die gleiche Richtung zeigen
(hab mir gerade ein kleines programm geschrieben, das per rand() alle möglichen Größenänderungen durchprobiert aber hab bisher noch nix funktionierendes gefunden)

jemand ne idee? :ugeek:

[Stephan Theisgen]

^gutes Argument

[Schrompf]

Sehe ich das richtig, dass das ganze Problem nicht existiert, wenn Du einfach ein neues Array aufmachst und intern rüberkopierst? Dann mach doch das erstmal. Nach meiner Erfahrung sind nämlich Größenänderungen sehr selten, bei denen eine Dimension verkleinert und eine andere vergrößert wird. Entweder werden alle Dimensionen vergrößert oder verkleinert, oder nur eine Dimension und die anderen bleiben stabil.

[BeRsErKeR]

Ich kann mich Schrompf nur anschließen. Und vorallem wie oft tritt denn der Fall

Es soll nicht bei jedem ändern der Größe neuer Speicher allokiert werden, sondern, wenn der bereits allokierte Speicher für die neue Größe des Arrays ausreicht, dieser Speicher weiterverwendet werden.

auf? Eigentlich sollte so ein Fall nicht unbedingt oft auftauchen und vorallem nicht in zeitkritischen Bereichen. Da du außerdem ziemlich viel zerpflücken müsstest und somit vermutlich sehr viele Kopieraktionen von kleinen Teilen durchführen musst, weiß ich auch nicht ob das unbedingt besser ist, als das ganze komplett zu kopieren.

Was mich besonders stört ist auch, dass du aus einem "Objekt" ein ganz anderes "Objekt" erstellst und dennoch den gleichen Platz im Speicher verwendest. Für mich ist das schon von der logischen Seite her nicht unbedingt wünschenswert. Zumal du ja sicher nicht nur von 2,3dim-Array zu 3,2dim-Array etc. transformierst, sondern z.B. auch von 3,3dim auf 2,2dim und du dann gff. unnützerweise viel zu viel Speicher blockierst.

Ist denn die Allokation in deinem Fall so störend, dass du sie aus welchen Gründen auch immer, nicht durchführen willst/kannst?

[B.G.Michi]

Also es ist möglich und das muss auch für beliebige Dimension und Größenänderung so sein, da die Reihenfolge der Objekte im Speicher ja nie verändert wird. Nach einigem Rumprobieren hab ichs dann hinbekommen: des Rätsels Lösung war im Endeffekt doch Stephans Vorschlag mit dem Mapping, nur kann ich nicht entweder von vorne oder von hinten durchlaufen.

Eigentlich isses ganz einfach: es wird von vorne durchgelaufen und für jedes Objekt berechnet, wie weit und in welche Richtung es verschoben werden muss, indem man aus den "Koordinaten" die Speicherstelle vor und nach der Größenänderung berechnet. Man läuft so lange durch den Speicher von vorne nach hinten und verschiebt die Objekte, so lange diese nach vorne verschoben werden müssen (so wird hier nie ein Objekt überschrieben). Findet man nun ein Objekt das nach hinten verschoben werden muss und würde dies tun, so könnte man weiter hinten liegende Objekte überschreiben. Also merkt man sich die aktuelle Position (pos1) und sucht man so lange weiter, ohne etwas zu verschieben, bis man wieder ein Objekt findet, das nach vorne verschoben werden muss oder man am Ende des Arrays ankommt. Jetzt merkt man sich nochmal die aktuelle Position (pos2) und verschiebt erst jetzt alle Objekte zwischen pos2 und pos1 und zwar diesmal von hinten nach vorne. Danach macht man bei pos2 weiter und wiederholt das ganze Spielchen so lange bis man durch das Array durch ist.

Das Verfahren ist nicht so wahnsinnig performant. Für kleine Objekte oder solche mit niedrigem Kopieraufwand ist es eine Menge Overhead. Aber es funktioniert. Für 1D- und 2D-Arrays wird dann einfach spezialisiert.
Ich bedanke mich für die Hilfe :D