spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ich bevorzuge letztere, da ich eigentlich immer im Kopf habe, dass zuerst die rows und dann die columns kommen. Einen wirklichen Standard gibt es da meines Wissens auch nicht, hauptsache du wirfst es nicht zwischen durch durcheinander.

Hallo,

es passt zwar nicht so ganz, aber ich werfe es trotzdem mal in den Raum.

Da man 2D Arrays in C++ so schlecht übergeben kann, bin ich irgendwann dazu über gegangen alles in einem 1D Array abzubilden.



Schöne Grüße

fb

Arrays will man eh nicht mehr benutzen. Eigentlich möchte man std::vector benutzen, wenn die Größe statisch sein soll, ist auch std::array eine gute Idee (wobei ich es für wahrscheinlich halte, dass man unterschiedliche Größen unterstützen möchte, d.h. eher std::vector).

Hier hat man jetzt auch wieder die Wahl, ob man 2 vectoren verschachtelt, oder einen eindimensionalen benutzt. Der Vorteil des eindimensionalen ist der, dass man nur ein vector Objekt mit einem großen Speicherblock hat. Man kann dann ähnliche Zugriffsfunktionen wie die von Fireball benutzen. Ein wenig Cooler ist aber so etwas:

Man gibt also eine Referenz auf das Objekt zurück, so dass man mit den Elementen ganz normal rechnen kann und sie nicht holen, manipulieren und dann wieder setzen muss.
Wenn man noch cooler sein möchte, kann man sich auch ein Proxy-Objekt bauen:


Das ist ein hübscher Trick, wie man mit etwas mehr Aufwand in der Klasse, ein deutlich angenehmeres Interface hinbekommt. Natürlich würde man das noch erweitern und als Template bauen und so weiter. Das ist eine sehr schöne Übung, allerdings hat das alles natürlich schon jemand gemacht:


http://www.boost.org/doc/libs/1_55_0/lib…y/doc/user.html


(Das waren jetzt einige, sagen wir, fortgeschrittene C++ Techniken, aber es zeigt, was man letztendlich alles so machen kann.)

Wozu ein std::vector, wenn es ein std::array auch täte?
std::array<std::array<T, y>, x>
Darüber lässt sich aber eindeutig streiten. Letztlich ist Vector intern fast dasselbe und ist flexibler.
T[] zu verwenden ist meist aber nicht mehr state of the art.

Ich bin übrigens für [x][y]. Das entspricht jeder Call-Convention bei Grafik-Bilbiotheken, die immer erst x und dann y übergeben. Alles andere ist verwirrend.
Allerdings muss ich auch sagen, dass Marble Theory genau andersrum mit Map.Colums[y].Row[x] arbeitet Da das aber eindeutig ist, was Rows und was Columns sind, sehe ich hier kein Problem mit Verwirrung.
Falls Deine Algorithmen immer in Loops zeilenweise wie ein Drucker/Monitor arbeiten, ist es für Caching allerdings besser es [y][x] zu bauen.

Ich stimme da BlueCobold zu. Habe da am Anfang selbst teilweise Probleme gehabt, weil ich gehört und gelesen habe dass

besser sein soll. Die Erklärung ist wie BlueCobold auch anreißt die Variante wie man über die Struktur iteriert. Wenn man nicht groß nachdenkt schreibt man sowas wie:



Das ist nicht sonderlich effizient. Das liegt an der internen Darstellung des 2D Arrays, welches am Ende ja einfach zusammenhängender Speicher ist. Bei dieser Variante der Indizes sollte man nicht zeilen- sondern spaltenweise iterieren. Das ist am Ende auch schon alles. Ich mag die Schreibweise von Map[x][y] da es meinem Verständnis von Koordinatenübergabe entspricht. Erst kommt die X Koordinate, dann die Y Koordinate. Gewöhn dir am besten direkt eine Variante an damit du nicht durcheinander kommt. Welche Datenstruktur man dann am Ende jeweils wählt hängt natürlich vom Problem ab. Das wäre aber auch erst mal unabhängig hiervon.

Grundsätzlich: Verwende immer std container. Die sind, im Zweifelsfall, immer effektiver und auch einfacher zu verwenden. Außerdem wirst du sie später, wenn du mal größere Sachen programmierst, eh nur noch verwenden wollen und da macht es keinen Sinn, sich jetzt andere Sachen anzugewöhnen. Kann mich schon gar nicht mehr daran erinnern, wann ich zuletzt ein normales array verwendet habe.

Das mit den STD Containern ist schon richtig. Die sind um einiges moderner und da solltest du dich wirklich dran gewöhnen. Wirklich komplizierter sind sie für dich eigentlich nicht. Im Endeffekt sind sie eigentlich sogar um einiges leichter zu benutzen. Was den Laufzeitunterschied angeht, so kannst du das selbst ganz leicht testen. Iterier doch einfach mal über ein 2D Array und weise einfach nur einfache Werte zu. Miss die Zeit die dafür gebraucht wird. Dann machst du das selbe mit der anderen Variante:


So in etwa wäre der Pseudocode. Übersetzen kannst du dir das ganze ja relativ einfach. Warum das eine schneller ist als das andere liegt an den einzelnen Speicherzugriffen. In einem Array liegen die Werte direkt hintereinander im Speicher. Wenn du nun ein Array von Arrays machen würdest, so ist der gesamte Speicher auch am Stück. Nur entweder läufst du den gesamten Speicher von vorne durch, oder du springst immer hin und her. Je nachdem in welcher Reihenfolge du durch das Array iterierst. Mal dir das ganze mal auf, dann wirds vielleicht deutlicher. Was das ausmachst kannst du selbst sehen wenn du mal den Code oben als Programm umsetzt. Wichtig ist nur, mach die Arrays groß genug. Je größer, desto deutlicher siehst du den Unterschied.

Der eigentliche Grund ist aber, dass Speicherzugriffe nicht immer gleich lange dauern.

Um den Zugriff auf den Hauptspeicher zu beschleunigen, verfügen Prozessoren über Caches, kleine Zwischenspeicher. Davon kann es auch mehrere Stufen geben, und ganz am Ende stehen Daten in den Registern des Prozessors, wo der Zugriff am schnellsten ist.
Da es wenig Sinn macht, jedes Datum einzeln in den Cache zu laden, und da man beobachtet, dass Daten die im Speicher eng zusammen liegen, auch meistens in ihrer Benutzung eng zusammen liegen, schreibt man sie sozusagen schon auf verdacht in den Cache.
Iterierst du also so über die Daten, wie sie im Speicher liegen, hast du die optimale Performance. Benutzt du einen eher wahlfreien zugriff (so sieht es zumindest aus, wenn du in umgekehrter Reihenfolge iterierst), musst du andauernd andere Daten in den Cache laden, was langsamer ist. Das Stichwort wäre Cache-Miss. Mehr dazu hier:
https://de.wikipedia.org/wiki/Cache

Der einzige Grund, weshalb ich [y][x] geschrieben habe, ist übrigens der, dass mein Proxy-Objekt eben so herum funktionierte. Wer aber das Prinzip verstanden hat, kann den Code natürlich umschreiben, so dass man am Ende [x][y] benutzten kann. Zu beachten ist, dass sich dadurch das Speicherlayout nicht ändert, da einfach nur die Position anders berechnet wird.