Wie speichert man Arrays im Speicher des Computers?
Und wie sieht der Zugriff aus?

Dieser Artikel beschreibt, was alles nötig ist, um ein Array im Speicher abzulegen und auf die Element zugreifen zu können. 

Wenn man normalerweise von  Arrays redet, dann meint man die Struktur und ihren Inhalt. Unter der Struktur meint man dann die Aufstellung der ArrayElemente.
Die Elemente (Integer oder andere ordinäre Typen) werden dabei alle hintereinander im Speicher dargestellt. Das erscheint logisch, denn Speicher ist nur linear (also eindimensional).

 Das Problem bei diesem Ansatz ist, dass man dann immernoch nicht vom Aufbau des Arrays gesprochen hat. Unter dem Aufbau des Arrays versteht man dabei, die Anzahl der Dimensionen und deren Ober- und Untergrenzen. Zudem muss man noch die Komponentengröße im Speicher kennen, damit man im Speicher ein Element überspringen, und so zum nächsten Element gelangen kann. Den Aufbau des Arrays muss zusätzlich zum Arrayinhalt gespeichert werden. Weil der Aufbau so wichtig ist, hat dieser einen eigenen Namen : Dope.

Ein eindimensionales Array ist noch ziemlich einfach. Ich werde daher zeigen, was man im Falle eines zweidimensionalen Arrays machen kann. Beliebig viele Dimensionen gehen analog. Siehe dazu auch den Wikeintrag zu Array .

Beispiel: 

 Array[1..2, 1..3] of Byte = {(1,2),(3,4),(5,6)}

 Die erste (x) Dimension hat also 2 Elemente, die zweite Dimension 3 Elemente.

 Wir können diese Matrix auf zwei Arten linear machen :

1. Speichern der Elemente zeilenweise
(hinterer Koordinatenwert läuft schneller als vorderer)

Koordinaten [x,y]: [1,1][1,2][1,3][2,1][2,2][2,3]
Werte: 1,2,3,4,5,6

2. Speichern der Elemente spaltenweise
(hinterer Koordinatenwert läuft langsamer als vorderer)

Koordinaten [x,y] : [1,1][2,1][1,2][2,2][1,3][2,3]
Werte: 1,4,2,5,3,6

Wir werden zuerst die zeileweise Darstellung besprechen : 

 Das Problem ist nun, wie man bei der zeilenweisen Darstellung beispielsweise an das Element 3 gelangen kann.
Eine erste Überlegung mag sein, dass man einfach 2 Elemente einfach überspringt. Das ist auch nicht falsch. Aber wir wollen ja wissen, wie man das berechnen kann.

Mit den Informationen aus dem Dope kann man das ganz einfach berechnen.

Der Dope sieht folgendermasen aus:

Wie kennen schon die Daten von 1 bis 5 aus der Array defintion oben.
Eine Eigenart des zeilenweise Dopes ist, dass die Größe des zu speichernden Elements in L₂ gespeichert wird. Wir haben hier ein Byt, deshalb also 1.

 L₂ ist also eine Variable mit dem Index 2, wobei 2 hier die Dimensionsgröße des Arrays (2) angibt. Die Elementgröße wird
also bei zeilenweißer Darstellung immer im L mit dem Index der Dimensionsgröße gespeichert. (hier L2)

Alle anderen L's (hier nur noch L1) werden berechnet und müssten eigentlich garnicht im Dope gespeichert sein.
 Die Rechnung für L1 sieht bei zeilenweiser allgemein Darstellung so aus :

 L_i = (OG_(i+1) - UG_(i+1) + 1) * L_(i+1)

Bei der (zeilenweisen) Berechnung ist das L der Dimension i also immer von der Dimension mit der größeren Zahl abhängig. Hier also Dimension 1 (i=1) von Dimension 2.

Wir berechnung nun also (dynamisch) L1 :

L₁ = (OG₂ - UG₂ + 1) * L₂ = (4 - 2 + 1) * 1 = 3 * 1 = 3

Die Zeile 7 ist im Dope eigentlich nicht notwendig, da wir sie aus den gegeben anderen Zeilen leicht berechnen können.

Wir können nun jede Position eines Elements im Speicher berechnen.
Array[x,y]

Die Vorschrift dazu lautet :

(1 bis dim)Σ (index_i - UG_i)*L_i

In Worten :
Für alle Indizes in Array (also hier x und y) : subtrahiere die Untergrenze der Dimension (x = 1 und y = 2) ab
und multipliziere jede Subtraktion mit der Komponentengrösse L der Dimension.

Beispiel :

Array[2,3] = 5 (Wert)

Die Werte stehen so im Speicher :

1,2,3,4,5,6

Nach der obigen Vorschrift wird die Position von 5 im Speicher so berechent :
(2 - UG1) * L1 + (3 - UG2) * L2 =
(2 - 1) * L1 + (3 - 2) * L2 =
1 * 3 + 1 * 1 =
3 + 1 = 4

Wir müssen also 4 Elemente überspringen um das Element 5 lesen zu können.

Wir werden nun die spaltenweise Darstellung besprechen : 

 Das Problem ist hier nun, wie man bei der spaltenweise Darstellung beispielsweise an das Element 5 gelangen kann.
Eine erste Überlegung mag sein, dass man einfach 3 Elemente einfach überspringt. Das ist auch nicht falsch. Aber wir wollen ja wissen, wie man das berechnen kann.

Mit den Informationen aus dem Dope kann man das ganz einfach berechnen.

Der Dope sieht folgendermasen aus:

Wie kennen schon die Daten von 1 bis 5 aus der Array defintion oben.
Eine Eigenart des spaltenweise Dopes ist, dass die Größe des zu speichernden Elements in L₁ gespeichert wird. Wir haben hier ein Byte als Dantentyp, deshalb also 1.

 L₁ ist also eine Variable mit dem Index 1, wobei 1 hier die kleinste Dimensions des Arrays (1 von 2) angibt. Die Elementgröße wird
also bei spaltenweiser Darstellung immer im L mit dem Index der kleinsten Dimension gespeichert. (hier L1)

Alle anderen L's (hier nur noch L2) werden berechnet und müssten eigentlich garnicht im Dope gespeichert sein.
 Die Rechnung für L2 sieht bei zeilenweiser allgemein Darstellung so aus :

 L_i = (OG_(i-1) - UG_(i-1) + 1) * L_(i-1)
Im Gegensatz zu zeileweise Darstellung, werden hier statt (i+1) einfach (i-1) verwendet.

Bei der (spaltenweise) Berechnung ist das L der Dimension i also immer von der Dimension mit der eins kleineren Zahl abhängig. Hier also Dimension 2 (i=2) von Dimension 1.

Wir berechnung nun also (dynamisch) L2 :

L2 = (OG₁ - UG₁ + 1) * L1 = (2 - 1 + 1) * 1 = 2 * 1 = 2

Die Zeile 7 ist im Dope eigentlich nicht notwendig, da wir sie aus den gegeben anderen Zeilen leicht berechnen können.

Wir können nun jede Position eines Elements im Speicher berechnen.
Array[x,y]

Die Vorschrift dazu lautet genauso wie bei der zeilenweisen Berechnung:

(1 bis dim)Σ (index_i - UG_i)*L_i

In Worten :
Für alle Indizes in Array (also hier x und y) : subtrahiere die Untergrenze der Dimension (x = 1 und y = 2) ab
und multipliziere jede Subtraktion mit der Komponentengrösse L der Dimension.

Beispiel :

Array[2,3] = 5 (Wert)

Die Werte stehen so im Speicher :

1,4,2,5,3,6

Nach der obigen Vorschrift wird die Position von 5 im Speicher so berechent :
(2 - UG1) * L1 + (3 - UG2) * L2 =
(2 - 1) * L1 + (3 - 2) * L2 =
1 * 1 + 1 * 2 = 
1 + 3 = 3

Wir müssen also 3 Elemente überspringen um das Element 5 lesen zu können.

Geschrieben von Christian Wimmer @ 2007 v0.1