2 dimensionale vectoren

!!!Achtung: Dieser Artikel ist veraltet. Ich lasse ihn dennoch für alle lesbar, da trotzdem noch viel (meiner Meinung nach) richtiges enthalten ist!!!

 

Da ich mich in letzter Zeit immer mal wieder darüber geärgert habe, dass ich noch keine wirklich gute Implementierung für einen 2 dimensionalen vector geschrieben habe, und ständig verschachtelte Konstrukte zweier vectoren genutzt habe, habe ich mich mal dran gesetzt und ein wenig herum experimentiert. Ich habe natürlich nicht das Rad komplett neu erfunden, sondern habe mich an existierende Ideen gehalten.

In dem nachfolgenden Beitrag versuche ich die Nachteile der verschachtelten vectoren zu erklären und die generelle Funktionsweise von einem internen vector vorzustellen.

 

Nachteile der Verschachtelung:

Eine verschachtelte Datenstruktur ist im Prinzip folgendes:
std::vector<std::vector<T>>
Man hat hier also einen vector, der vectoren mit ints hält, um eine 2 dimensionale Datenstruktur zu simulieren. An sich ist diese Idee gar nicht so falsch, denn hier kann man direkt über die at Methoden oder die [] Operatoren auf die Einträge zugreifen. Warum das allerdings keine wirklich gute Idee ist, soll der nachfolge Text verdeutlichen.

Um dieses System sicher nutzen zu können, ist es zwingend erforderlich, eine eigene Klasse um den vector zu bauen, da ansonsten nicht sichergestellt werden kann, dass bei einer Größenänderung alle Zeilen und Spalten betroffen sind, da man ansonsten sehr schnell einen out of range error hervorruft oder unnötig Speicherplatz verschwendet.
Durch die Verschachtelung, kann man nun nicht alle inneren vectoren auf einmal verändern, sondern muss diese nacheinander bearbeiten und das kann unter Umständen sehr zu lasten der Performance gehen, da pro Zeile oder Spalte (je nachdem, wie man seine Datenstruktur anlegt) eine Allocation benötigt, die potentiell erst einmal teuer ist. Man kann sich das z.B. so vorstellen, als würden bei einem Imbiss mehrere Leute Pommes bestellen, und der Imbiss frittiert jede Portion einzeln nacheinander, statt alle zusammen auf einmal. Das verlängert nicht nur die Zeit, die man für die einzelnen Kunden benötigt, sondern macht diese auch unzufrieden. Die unzufriedenen Kunden wären in diesem Fall die Nutzer des Programms 😉
Da in einem vector alle Daten hintereinander im Speicher liegen, ist das Vergrößern/Verkleinern noch einmal doppelt teuer, da der nachfolgende Speicher erst einmal weiter nach hinten verschoben werden muss, damit zwischendrin Speicher angefordert werden kann. Die nachfolgenden Bilder sollen das oben genannte Problem veranschaulichen.

4x4Vector
Dieses Bild stellt einen logischen 3×3 vector dar. Das ist NICHT die Darstellung für den intern genutzten Speicher.

 

 

 

 

6x4VectorAlloc
Wieder eine Darstellung eines logischen 2 dimensionalen vectors. Diesmal jedoch mit einer Größe von 5×3. Die gestrichelten Kästchen stellen den neu allokierten Speicher dar. An sich sieht das ganz vernünftig aus, schauen wir uns allerdings mal an, was im Hintergrund wirklich passiert.

 

 

Die folgenden Bilder zeigen den Zusammenhang des internen Speichers und soll die Problematik beim Vergrößern ein wenig besser illustrieren.

4x4VectorMemory

Wie man hier gut sieht, sind die Speicherblöcke der einzelnen Zeilen direkt hintereinander im Speicher. Das ist auch gut so, da so ein Zugriff auf jede dieser Zellen in konstanter Zeit erfolgen kann. Was aber getan werden muss, wenn wir unsere Struktur vergrößern, zeigt das nächste Bild.

 

6x4VectorMemoryAlloc

Dieses Bild stellt die Schritte dar, die für die 3 Zeilen durchgeführt werden, wenn man sie auf die oben erklärte Art und Weise ausführt.

  1. 2 zusätzliche Blöcke werden angefordert und die Zeilen 2 und 3 werden im Speicher nach hinten geschoben, um Platz zu schaffen
  2. Wieder werden 2 Blöcke angefordert (diesmal um die Zeile 2 zu vergrößern) und Zeile 3 wird nach hinten geschoben.
  3. 2 Blöcke werden angefordert, und an Zeile 3 angehängt

Wie man sieht, sind 3 allocationen nötig und Zeile 2 wird einmal und Zeile 3 sogar 2 mal verschoben. Leider ist das sogar der optimale Fall.
Wenn der vector in einem Speicherbereich liegt, der nicht genug Platz zum Vergrößern bietet, wird die gesamte Struktur verschoben, und nicht nur die dahinter liegenden Zeilen. Das kann auch bei jeder Vergrößerung einer Zeile passieren. Wenn man also seine Klasse öfter transformiert, wird die Performance bei einer gewissen Anzahl an Elementen deutlich leiden.

 

Das ein vector System

Wie also gerade beschrieben, ist es sinnvoller den Speicherplatz einmal zu reservieren, statt stückchenweise, allerdings ist das mit dieser Struktur nicht möglich.
Aus diesem Grund bietet es sich an, EINEN großen vector zu nutzen, diesen einmal zu vergrößern/verkleinern und die Daten intern EINMAL zu verschieben.
Trotzdem können wir die einzelnen Zellen genau bestimmen. Die Formel für den Index einer Zelle ist ziemlich einfach.
index = y * breite + x
Möchten wir also bei einem vector von 3 x 3 (9 Zellen) auf die Zelle x = 0 und y = 0 zugreifen, erhalten wir einen internen Index von 0 (das erste Element im vector), bei x = 2, y = 1 wäre der Index 6.

Aber wie können wir das Ganze nun transformieren?

Um diesen vector zu transformieren, benötigen wir die neue und die alte Größe. Es bietet sich an, diese beiden Dimensionen (also Höhe und Breite) getrennt von einander zu behandeln.
Neue Zeilen anzufügen ist sehr trivial. Wir vergrößern den vector um
(neueHöhe - alteHöhe) * breite
Elemente. D.h., wenn wir unseren 3 x 3 vector um 2 Zeilen erweitern wollen, fügen wir
5(neueHöhe) - 3(alteHöhe) * 3(breite) = 6
Zellen hinten an. Da wir nichts zwischen unseren alten Daten verändern, müssen wir diese auch nicht verschieben.
Schematisch dar gestellt, sieht das folgendermaßen aus:

Vector2DresizeHeight
Hier kann man ganz gut sehen, das hier die Zeilen hintereinander liegen, und deswegen die bereits vorhandenen Zeilen nicht verändert werden.
Jedoch ist auch hier nicht garantiert, dass der Vector an der momentanen Speicherposition genug Platz hat. Deswegen ist es möglich, dass er an eine andere Adresse verschoben wird. Allerdings passiert das garantiert nur einmalig und ist auch eine vergleichsweise sehr günstige Operation. Zudem können wir das auch gar nicht erst verhindern, da das im Hintergrund passiert. Wichtig ist jedoch, dass Referenzen und Zeiger auf Elemente innerhalb dieses Vectors danach ungültig sein können!
Das Verkleinern funktioniert im Prinzip genau gleich. Auch hier muss nichts verschoben werden, da die zu löschenden Daten bereits am Ende liegen.

Die Breite wird mit der gleichen Formel verändert, allerdings müssen wir jetzt intern noch die bereits vorhandenen Daten verschieben, damit sie am Ende auch an der richtigen Stelle stehen.
Dazu zuerst mal eine schematische Darstellung.

Vector2DresizeWidth
Wie man sieht, kann hat man hier ein bisschen mehr Arbeit, als beim Höhen verändern, ist aber prinzipiell auch recht einfach. Damit wir jede Zeile nur einmal verschieben müssen, fangen wir an, uns von hinten nach vorne zu arbeiten, weil wir sonst möglicherweise noch zu verschiebende Einträge überschreiben würden. D.h. zuerst auf die benötigte Breite festsetzen und dann die vorhandenen Elemente entsprechend nach hinten verschieben.
Beim Verkleinern arbeiten wir uns diesmal von vorne nach hinten und verschieben die Einträge, die behalten werden sollen, nach vorne.

Je nach Bedarf, kann man nun seine vector2D Klasse die Iteratoren von std::vector nach außen anbieten, und damit eine Iteration von außen über alle Elemente ermöglichen.

 

Zeilen und Spalten Modelle

Jetzt kommen wir zu einem Bereich, der bei solchen Implementierungen oft vergessen wird. Wir haben nun einen funktionierenden 2 dimensionalen vector und Zugriff auf alle Elemente. Wenn wir aber nur über eine Spalte/Zeile iterieren wollen, sind wir gezwungen, das über die Indexes zu machen.
Das hat aber den Nachteil, dass keine Funktionen genutzt werden können, die Iteratoren erwarten.
Dazu habe ich folgende Lösung entwickelt:
Die Vector2D Klasse stellt Methoden bereit, die eine Art „Modell“ ihrer Zeilen und Spalten zurück liefert. Diese Modelle beinhalten lediglich einen Index auf die Zeile/Spalte und eine Referenz auf das Vector2D Objekt. Diese Modelle bieten direkten Zugriff auf die darunter liegenden Elemente der Zeile/Spalte und stellen auch Iteratoren bereit. Prinzipiell nicht sonderlich kompliziert.

Mit diesen Modellen können wir nun die range based for Loops und andere nette Dinge nutzen, die uns vorher verwehrt geblieben sind.

Eine vollständige Implementierung und Dokumentation des oben beschriebenen Systems findet ihr hier:
Vector2D.h
Dokumentation

 

Ich freue mich über jedwede Kritik und Kommentare

mfg

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.