spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Zitat von »eXpl0it3r«

Zitat von »dot«

Ein std::vector aus std::vector ist keine gute Lösung für ein zweidimensionales Array. Verwend besser einen einfachen eindimensionalen std::vector in dem du deine zweidimensionalen Daten z.B. zeilenweise speicherst...

Wie kommst du jetzt grad darauf?
Es mag zwar nicht sehr schön aussehen und ist ohne Iteratornutzung evtl. etwas weniger performant als ein wirkliches 2D Array, aber für einen kleinen Datensatz spielt dies alles keine Rolle.

Mit dem gleichen Argument könnte man auch eine verschachtelte std::map verkaufen...
Es geht mir nicht um die Performance. Ein verschachtelter std::vector entspricht einem sog. jagged Array, was rein prinzipiell etwas fundamental anderes ist als ein mehrdimensionales Array. Der Grund, wieso ich davon abrate, ist in erster Linie, dass es strukturell nicht dem zu lösenden Problem entspricht. Die Tatsache dass es auch noch unnötig ineffizient ist, spielt hier vermutlich tatsächlich keine Rolle. (Übrigens potentiell nicht nur ein bisschen und mit Iteratoren hat das nix zu tun, aber egal)

Zitat von »eXpl0it3r«

Du kennst ja sich das bekannte Zitat:

Zitat

Premature optimization is the root of all evil.

Ja, das berühmte Zitat von Donald E. Knuth, das, völlig aus dem Kontext gerissen, immer und überall verwendet wird, um alles Mögliche zu rechtfertigen...

Zitat von »eXpl0it3r«

Also verwirr die Anfänger doch nicht mit optimierungs Problemen.

Wie gesagt, handelt es sich da imo nicht einfach um ein Optimierungsproblem, sondern um etwas Prinzipielles...

Zitat von »eXpl0it3r«

Prinzipien haben immer einen Hintergrund und der einzige Grund, warum jagged Arrays nicht gut sind, ist weil es nicht sehr performant für die CPU bzw. deren Cache ist und darum die ganze Zeit Daten vom langsamen RAM angefordert werden müssen.

Das sind alles Gründe, aber nicht die einzigen. Ein imo noch viel wichtigerer Grund ist, dass jagged Arrays vergleichsweise sehr viel komplizierter sind als normale Arrays. Wieso sollte man eine kompliziertere einer sehr viel einfacheren Lösung vorziehen, wenn die einfachere sogar auch noch effizienter ist!?

Zitat von »eXpl0it3r«

Zitat von »dot«

Der Grund, wieso ich davon abrate, ist in erster Linie, dass es strukturell nicht dem zu lösenden Problem entspricht.

Wieso sollte dann ein eindimensionales Array von der Struktur her besser sein für das Problem?

Weil das Problem zweidimensionaler Natur ist und ein zweidimensionales Array hier die einfachste, intuitivste und effizienteste mir bekannte Lösung ist.

Zitat von »eXpl0it3r«

Für den Vorschlag wäre es evtl. für Anfänger noch hilfreich, wenn du ein Beispiel geben kannst, weil "Verwend besser einen einfachen eindimensionalen std::vector in dem du deine zweidimensionalen Daten z.B. zeilenweise speicherst..." sagt ja jetzt wirklich nicht viel aus.

Ich möchte unserem Anfänger eben die Chance geben, selbst zu denken und dabei wirklich was zu lernen anstatt vorgekaute Brocken zu kopieren. Für mich war genau diese Arraygeschichte damals eine sehr wichtige Erkenntnis...

Zitat von »eXpl0it3r«

dot, da ich mich für solche Design Prinzipien sehr interessiere, wäre ich froh wenn du das Ganze etwas ausführen könntest, weil bis jetzt habe ich noch nie gehört, dass zweidimensionale std::vector im Allgemeinen eine schlechte Datenstruktur ist.

Ich würde auch gar nicht sagen, dass es im Allgemeinen eine schlechte Datenstruktur ist. In den üblichen Fällen, wo man ein herkömmliches, mehrdimensionales Array haben will, ist ein jagged Array allerdings tatsächlich keine gute Lösung.

Beachte: Wir sprechen hier von einem std::vector, dessen Elemente selbst vom Typ std::vector sind. Die entstehende Datenstruktur ist zwar zweidimensional, es handelt sich dabei aber eben um eine ganz bestimmte Art einer zweidimensionalen Datenstruktur die sich, wie wir gleich sehen werden, fundamental von dem, was man sich normalerweise unter einem zweidimensionalen Array vorstellt, unterscheidet.

Zitat von »eXpl0it3r«

Auch bin ich mir über deine Definition/Vorstellung von Jagged Array nicht ganz bewusst, Google lieftert mir da eigentlich nur Artikel zu C#.

Unter einem Jagged Array versteht man ein Array aus Arrays, wobei jedes dieser Unterarrays eine andere Länge haben kann (hence the name). Im zweidimensionalen Fall sieht das also z.B. so aus:


Und genau so etwas ist auch unser std::vector<std::vector<T>>, denn ein std::vector<T> ist ein Array dynamischer Länge aus T und ein std::vector<std::vector<T>> ist damit ein Array dynamischer Länge aus Arrays dynamischer Länge aus T.

Eigentlich wollen wir aber einfach nur sowas


Natürlich kann man sowas als Spezialfall eines jagged Array betrachten und in einem std::vector<std::vector<T>> speichern. Das ist aber sicherlich keine besonders gute Lösung, denn wir bedienen uns damit einer für unsere Anwendung in absolut jeder nur erdenklichen Weise unnötig komplizierten Datenstruktur. Alles was wir eigentlich haben wollen, ist ein Speicherblock der M*N Elemente vom Typ T enthält. Ein std::vector<std::vector<T>> entspricht aber einem Speicherblock der die Adressen sowie Größen weiterer Speicherblöcke enthält, die dann erst die eigentlichen Daten enthalten. Ein std::vector<std::vector<T>> ist also schonmal gar kein zusammenhängender Block mehr, sondern im Allgemeinen fragmentiert; der Zugriff auf ein Element entspricht naturgemäß einer dopppelten Indirektion. Anstatt also direkt die Adresse des Elements auszurechnen und darauf zuzugreifen, müssen wir erst die Adresse der Adresse der Zeile/Spalte, die das Element enthält, berechnen, uns von dort die Adresse der Zeile/Spalte holen und dann die Adresse des Elements berechnen und darauf zugreifen. Die Speicherung der Länge jeder Zeile/Spalte ist natürlich zusätzlich redundant. Nichtmal ein einziger all der Aspekte, die sämtliche Komplexität dieser Datenstruktur ausmachen, ist für unsere Anwendung auch nur teilweise interessant.

Zitat von »eXpl0it3r«

Zitat von »dot«

Mit dem gleichen Argument könnte man auch eine verschachtelte std::map verkaufen...

Die STL wurde so entworfen, dass die Verwendung von dessen Containern keinen grossen Einfluss auf die Laufzeit oder den Speicher hat. Obwohl es natürlich in den meisten Fällen keinen Sinn macht std::map's zu verschachtel, so werden die Prinzipien von C++ damit nicht verletzt.
Ich kann hier zwar meistens nur Behauptungen aufstellen, weil ich nicht den Standard gelesen habe, aber ich vertraue darauf, dass die Implementierungen von der STL und die Optimierungen von den Compilers die beste Performance für den gegebenen Code generieren.

Der Standard macht keine Aussage darüber, wie eine Implementierung genau auszusehen hat, aber ja, der Compiler wird in der Tat relativ optimalen Code für deinen std::vector<std::vector<T>> generieren. Leider ist diese Datenstruktur eben für das zu lösende Problem nicht optimal. Du kannst aber natürlich darauf vertrauen, dass der Compiler den bestmöglichen Maschinencode für deine suboptimale Lösung erzeugen wird...

Wenn du schreibst std::vector<std::vector<T>>, dann sagst du: Ich will ein Array dynamischer Länge aus Arrays dynamischer Länge aus T. Und genau das bekommst du auch. Dass du eigentlich ein Array dynamischer Größe aus NxM T wolltest, kann C++ nicht erraten.

Zitat von »eXpl0it3r«

Das Problem mit dem CPU Cache tritt eigentlich nur auf, wenn man falsch durch ein mehr dimensionales Array iteriert, sprich zuerst die Zeilen und dann die Spalten.

Richtig, wenn man von einem entsprechend großen, mehrdimensionalen Array in column major Memory Layout ausgeht. Ein std::vector aus std::vector ist nur eben etwas völlig anderes...

Zitat von »eXpl0it3r«

Zitat von »dot«

Zitat von »eXpl0it3r«

Zitat von »dot«

Der Grund, wieso ich davon abrate, ist in erster Linie, dass es strukturell nicht dem zu lösenden Problem entspricht.

Wieso sollte dann ein eindimensionales Array von der Struktur her besser sein für das Problem?

Weil das Problem zweidimensionaler Natur ist und ein zweidimensionales Array hier die einfachste, intuitivste und effizienteste mir bekannte Lösung ist.

Wie bist du jetzt wieder von einem eindimensionalen Array, wie vorgeschlagen in deinem ersten Post, auf ein zweidimensionales Array gekommen? Und wieso ist ein zweidimensionales Array besser als ein zweidimensionaler std::vector?

Ich meinte ein herkömmliches zweidimensionales Array, das üblicherweise eben über eine bijektive Abbildung zweidimensionaler Indices in einen zusammenhängenden eindimensionalen Speicherbereich implementiert wird...