2D-Array: [x][y] oder [y][x]?
-
Ob es deswegen wohl RAM heißt?
-
Caligulaminus schrieb:
CppNeuland schrieb:
Ach, da gibt es wirklich einen Standard für? Ich meine, es ist doch eher von Algorithmus vorgegeben, was in die inneren Schleife gehört. Wenn aber nur über alle Tupel durchiteriert werden muss, dann ist es doch piepegal was innen ist.
Beim Drüberiterieren ist die Anordnung im Speicher Performancerelevant.
Wenn ich eh alle Pixel durchgehen muss, dann ist es doch egal ob ich x oder y in der inneren Schleife habe. Ich verstehe die Logik hinter der Aussage nicht.
-
CppNeuland schrieb:
Wenn ich eh alle Pixel durchgehen muss, dann ist es doch egal ob ich x oder y in der inneren Schleife habe. Ich verstehe die Logik hinter der Aussage nicht.
Je nachdem, ob du zeilen- oder spaltenweise iterierst, passierst du die einzelnen Elemente entweder mit fortlaufender Adressierung oder hast dauernd Sprünge. Letzteres ist relativ cache-unfreundlich und daher tendenziell langsam.
-
Nexus schrieb:
CppNeuland schrieb:
Wenn ich eh alle Pixel durchgehen muss, dann ist es doch egal ob ich x oder y in der inneren Schleife habe. Ich verstehe die Logik hinter der Aussage nicht.
Je nachdem, ob du zeilen- oder spaltenweise iterierst, passierst du die einzelnen Elemente entweder mit fortlaufender Adressierung oder hast dauernd Sprünge. Letzteres ist relativ cache-unfreundlich und daher tendenziell langsam.
Nicht nur was den Cache angeht, sondern auch den eigentlichen Vorgang des Holens an sich. Wenn die Daten noch nicht im Cache sind und aus dem Hauptspeicher (SDRAM) geholt werden müssen, dann bekommt man durch das Springen ein Problem:
http://en.wikipedia.org/wiki/Prefetch_buffer
-
CppNeuland schrieb:
Ach, da gibt es wirklich einen Standard für? Ich meine, es ist doch eher von Algorithmus vorgegeben, was in die inneren Schleife gehört. Wenn aber nur über alle Tupel durchiteriert werden muss, dann ist es doch piepegal was innen ist.
Es ist kein Standard im Sinne eines ISO-Standards, aber darin, wie so ein array als "default" interpretiert wird: ist es eine Menge von untereinander angeordneten
Zeilen(Row-Major) oder aneinandergereihte spalten (column-major).Und wenn man in den Performancebereich geht, ändern sich die Algorithmen mit der Speicheranordnung. Bei Matrixzerlegungen wird dann zum Beispiel nicht A zerlegt, sondern A^T.
-
SeppJ schrieb:
Nexus schrieb:
CppNeuland schrieb:
Wenn ich eh alle Pixel durchgehen muss, dann ist es doch egal ob ich x oder y in der inneren Schleife habe. Ich verstehe die Logik hinter der Aussage nicht.
Je nachdem, ob du zeilen- oder spaltenweise iterierst, passierst du die einzelnen Elemente entweder mit fortlaufender Adressierung oder hast dauernd Sprünge. Letzteres ist relativ cache-unfreundlich und daher tendenziell langsam.
Nicht nur was den Cache angeht, sondern auch den eigentlichen Vorgang des Holens an sich. Wenn die Daten noch nicht im Cache sind und aus dem Hauptspeicher (SDRAM) geholt werden müssen, dann bekommt man durch das Springen ein Problem:
http://en.wikipedia.org/wiki/Prefetch_bufferIch habe doch keine Sprünge wenn ich vorher meine Reihenfolge von x uns y an den Algo angepasst habe und dementsprechend meine Datenstruktur anlege und darum geht es doch hier, ob man immer x,y oder y,x als Standard nimmt.
Wenn der Algo in der inneren Schleife x nimmt dann nimmt man die eine Reihenfolge und im anderen Fall halt die andere. Nur so vermeidet man doch die Sprünge der Speicherzugriffe, indem man immer die Datenstruktur anlegt, die dem Algo am besten die Daten liefert. Da kann es doch keinen Standard geben.
Oder sehe ich da was völlig falsch?
-
CppNeuland schrieb:
Oder sehe ich da was völlig falsch?
Ich glaube ja. Ich bin mir ehrlich gesagt nicht sicher, was du meinst. Was sollen denn x und y sein? Du scheinst irgendwie sehr viel Gewicht auf Namensgebung zu setzen, dabei sind Namen das Unwichtigste überhaupt.
-
Ich denke diese Präsentation wird dir helfen zu verstehen (ab Slide 14 wird es für dich interessant):
http://channel9.msdn.com/Events/Build/2013/4-329
-
Die ursprünglich Frage war:
Mir ist immer noch nicht ganz klar, ob ich bei 2D-Arrays zuerst die Y-Dimension oder zuerst die X-Dimension nehmen soll.
Meine Antworten zusammengefasst: Das hängt vom Algo ab was zuerst kommt. Wenn der Algo in der inneren Schleife x nimmt, dann sollte dies hintereinander im Speicher liegen, ansonsten halt y.
-
CppNeuland schrieb:
Die ursprünglich Frage war:
Mir ist immer noch nicht ganz klar, ob ich bei 2D-Arrays zuerst die Y-Dimension oder zuerst die X-Dimension nehmen soll.
Meine Antworten zusammengefasst: Das hängt vom Algo ab was zuerst kommt. Wenn der Algo in der inneren Schleife x nimmt, dann sollte dies hintereinander im Speicher liegen, ansonsten halt y.
Und was hat das mit X und Y zu tun? Aber ja: Die Antwort sollte sein, dass du deine Daten so organisierst, dass in der innersten Schleife über den rechtesten Index iteriert wird. Und jeweils so weiter, wenn es sich um mehr als zwei Verschachtelungen handelt.
-
X = X-Dimension
Y = Y-DimensionDie Bezeichner bezogen sich auf die, in Ausgangsfrage genannten, Daten.
