DevC++ Was sind arrays, und wozu dienen sie?

[Brauni90]

[...] wenn ich jetzt ( Reihe [0] [1] = x schreibe in welche der zwei Dimensionen wird dieser wert geaendert [...]

...

Stell dir dein Array als ein zusammenhängender Speicher vor.

char board[R][C]; Der Speicher könnte dann so aussehen:
R=0; C=0 | R=0; C=1 | R=0; C=2 | R=1; C=0 | R=1; C=1 | ... | R=2; C=2 (-> höhere Adressen)

Du greifst auf ein 'Element' des Arrays zu, nicht auf eine Dimension. Mehrdimensionale Array dienen lediglich der Übersichtlichkeit oder der Effizienz. Prinzipiell kann man alles mit einem eindimensionalen Array machen.

[...] wobei man noch hinzufügen muss, dass Arrays, die mehr als 3 Dimensionen haben, sehr unübersichtlich werden.

...

Kommt auf die Betrachtungsweise an

[Kyuu]

Mehrdimensionale Array dienen lediglich der Übersichtlichkeit oder der Effizienz.

...

Bessere Veranschaulichung ja, Effizienz nein. Um auf Elemente mehrdimensionaler Arrays zugreifen zu können, sind mehr Operationen nötig als es bei eindimensionalen Arrays der Fall ist. Arrays, egal welcher Dimension (dieser Begriff dient wirklich nur der Veranschaulichung) sind immer eindimensional im Speicher ausgelegt, so dass, um auf Elemente mehrdimensionaler Arrays zugreiffen zu können, Berechnungen notwendig sind.

Eindimensionales Array mit 12 Elementen:

Code:

im Speicher
-------------------------------------------------------------
| 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 | 11 |
-------------------------------------------------------------

bildlich
-------------------------------------------------------------
| 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 | 11 |
-------------------------------------------------------------

Zweidimensionales Array mit 4x4 Elementen:
(hier im Format xy; im Code wird man mit array[y][x] zugreifen)

Code:

im Speicher
---------------------------------------------------------------------------------
| 00 | 01 | 02 | 03 | 10 | 11 | 12 | 13 | 20 | 21 | 22 | 23 | 30 | 31 | 32 | 33 |
---------------------------------------------------------------------------------

bildlich
---------------------
| 00 | 01 | 02 | 03 |
---------------------
| 10 | 11 | 12 | 13 |
---------------------
| 20 | 21 | 22 | 23 |
---------------------
| 30 | 31 | 32 | 33 |
---------------------

(Nach dem gleichen Prinzip sind auch alle folgenden mehrdimensionalen Arrays aufgebaut: Die Elemente der vorherigen Dimension sind in der nächsten Dimension Reihen.)

Wie man sehen kann, beginnt die nächste Reihe immer am Ende der vorherigen Reihe. Um also auf ein Element zugreifen zu können, muss man den Offset berechnen, was wie folgt aussieht:

Für eindimensionale Arrays:

Code:

Offset = Länge(Element) * x

Für zweidimensionale Arrays:

Code:

Offset = Länge(Element) * Länge(ReiheX) * y + Länge(Element) * x

Für dreidimensionale Arrays:

Code:

Offset = Länge(Element) * Länge(ReiheZ) * Länge(ReiheX) * y + Länge(Element) * Länge(ReiheZ) * x + Länge(Element) * z

usw.

Man sieht, dass je mehr Dimensionen, desto mehr Operation sind nötig um auf die Elemente zugreifen zu können. Selbst wenn einige der Multiplikationen wegoptimiert werden können, da zur Kompilierzeit bekannt, kann man trotzdem davon ausgehen, dass der Rechneaufwand von Dimension zu Dimension steigt.

[Desmulator]

Soweit ich das irgendwie mal mit bekommen habe sind Arrays doch einfach nur Zeiger auf einen einfachen Speicherbereich in dem sich die Elemente des Arrays hinter einander befinden. Nun wenn ich jetzt ein mehr-dimensionales Array besitze, habe ich praktisch ein Array eines Arrays ...

Folglich komme ich zu dem Schluss, dass die Dinge nicht hintereinander sondern "willkührlich" im Speicher liegen. ( oder ist das in C/++ anders? )
Da das eine Array die Zeiger auf den anderen Speicher enthält wo sich die eigendlichen Elemente befinden.

[Kyuu]

Nein, die Elemente liegen alle nebeneinander und das wird bei allen Implementierungen statischer Arrays der Fall sein, weil die Lokalität für die Effizienz sehr wichtig ist. Das, was du meinst sind dynamische Arrays, die je nach Implementierung als Elemente auch Zeiger auf Arrays haben können, die woanders liegen. Nicht zu verwechseln mit dynamisch erzeugten statischen Arrays.

[Brauni90]

Habe mich wohl unverständlich ausgedrückt. Mit Effizienz war die Unterstützung durch Hardware gemeint, die im Gegensatz zur hausgemachten 'Implementierung in Software' dennoch einen Vorteil bringen kann. Eigentlich sind es nur Additionen und Multiplikationen. Aber das kann man auch anders implementieren um somit eine bessere Effizienz erreichen.

[Kyuu]

Hardwareunterstützung für den Zugriff auf mehrdimensionale Arrays? Davon lese ich zum ersten mal, wenn ich ehrlich sein soll. Was kann ich mir darunter vorstellen?

Eigentlich sind es nur Additionen und Multiplikationen. Aber das kann man auch anders implementieren um somit eine bessere Effizienz erreichen.

...

Falls es rübergekommen ist, als würde ich Zugriffe auf mehrdimensionale Arrays als langsam bezeichnen, so war das nicht beabsichtigt. Das ist natürlich vollkommener Quatsch, denn Integeradditionen und selbst -multiplikationen sind heute sehr schnell, Additionen und Subtraktionen benötigen z.B. nur einen Cycle und bei Operationen auf Arrays ist die Chance groß, dass man diese vektorisieren kann, was das Ganze nochmal um ein Vielfaches schneller macht.
Ich habe es nur so aufgefasst, als würdest du behaupten, Zugriffe auf mehrdimensionale Arrays wären schneller als auf eindimensionale.

[Mog]

Hardwareunterstützung für den Zugriff auf mehrdimensionale Arrays? Davon lese ich zum ersten mal, wenn ich ehrlich sein soll. Was kann ich mir darunter vorstellen?



Falls es rübergekommen ist, als würde ich Zugriffe auf mehrdimensionale Arrays als langsam bezeichnen, so war das nicht beabsichtigt. Das ist natürlich vollkommener Quatsch, denn Integeradditionen und selbst -multiplikationen sind heute sehr schnell, Additionen und Subtraktionen benötigen z.B. nur einen Cycle und bei Operationen auf Arrays ist die Chance groß, dass man diese vektorisieren kann, was das Ganze nochmal um ein Vielfaches schneller macht.
Ich habe es nur so aufgefasst, als würdest du behaupten, Zugriffe auf mehrdimensionale Arrays wären schneller als auf eindimensionale.

...

Boost-Mode\Heap, HW-Loops vlt?

[Kyuu]

Ich bin jetzt etwas verwirrt wieso du den zweiten Teil auch zitiert hast, denn dieser hat mit dem ersten nichts zu tun. Außerdem ist mir dein Kommentar zu minimalistisch, um daraus genügend Inhalt zu gewinnen. :0

Es ging mir übrigens nicht darum wie man sequentiellen Zugriff auf Arrays (Dimension irrelevant) hardwareseitig/softwareseitig optimieren kann, da hat man viele Möglichkeiten offen: software pipelining, loop unrolling, SIMD instructions, pointer arithmetic, etc., das ist alles eher uninteressant. Interessant ist ob die obligatorische Berechnung des Offsets bei Ausdrücken der Form 'array[a1]...[an]' hardwareseitig abgenommen werden kann.


Edit: @Mog:

Ah, danke für die Erklärung. :) Mit einem DSP hatte ich bisher nur sehr wenig zu tun (SSE), Hardware Looping ist für mich also Neuland.

[Mog]

Ich bin jetzt etwas verwirrt wieso du den zweiten Teil auch zitiert hast, denn dieser hat mit dem ersten nichts zu tun. Außerdem ist mir dein Kommentar zu minimalistisch, um daraus genügend Inhalt zu gewinnen. :0

Es ging mir übrigens nicht darum wie man sequentiellen Zugriff auf Arrays (Dimension irrelevant) hardwareseitig/softwareseitig optimieren kann, da hat man viele Möglichkeiten offen: software pipelining, loop unrolling, SIMD instructions, pointer arithmetic, etc., das ist alles eher uninteressant. Interessant ist ob die obligatorische Berechnung des Offsets bei Ausdrücken der Form 'array[a1]...[an]' hardwareseitig abgenommen werden kann.

...

Hardware-Loops. Steht doch dort. Genau dafuer sind die Dinger doch da. Jeder, der schon mal mit einem DSP gearbeitet hat, kennt diese Dinger eigentlich. Im Prinzip ist das nur ein Werk, welches for-schleifen mit einem Index optimal aufloest. Spich: Die Spruenge werden von der Hardware direkt serialisiert, und das Inkrement automatisch in einem Zug gebildet. Wohl gemerkt muss man diese per Hand verwenden - kein Compiler verwendet sie von Haus aus.

Zumindest diese passen nicht in den Haufen, den du gelistet hast. Boost ist wahrscheinlich bereits zu abstrakt, fuer einen Programmierer.

[Brauni90]

Hardwareunterstützung für den Zugriff auf mehrdimensionale Arrays? Davon lese ich zum ersten mal, wenn ich ehrlich sein soll. Was kann ich mir darunter vorstellen?

...

Das von Mog bereits beschriebene oder den Optimierungsspielraum, den man dem Compiler damit lässt, sofern dieser das berücksichtigt. Für die meisten Nutzer wird die heutige Hardware so oder so reichen, aber darum geht es nicht. Eher um ein Hinweis auf eine Überlegung zu den damit verbundenen möglichlichen Optimierungen bei Hardware ...

[Kyuu]

Ich habe durchaus nach konkreten Beispielen gefragt. ^^
Und Optimierungsspielraum lassen impliziert noch lange nicht gewonnene Effizienz.

BTW: Nach Michael A. Jackson lautet die erste Regel für Optimierung "Tu es nicht", die zweite "Tu es noch nicht" (im Sinne von "tu es erst, wenn Handlungsbedarf besteht"). Wenn man das befolgt, lässt man dem Compiler theoretisch sowieso den höchstmöglichen Optimierungsspielraum.