dynamisches Array

[Martin Sche. (Gast)]

Hallo Leute!

Ich muss ein 2D Array dynamisch erzeugen.
Es soll so aussehn:
array[p][k], wobei k eine feste, bekannte Größe ist und p vom Benutzer 
vorher eingeben wird.
Würde das gerne mit alloc machen, aber weiß nicht wie ich dem klar 
mache, dass das Array zweidimensional ist.
Grundsätzlich hät ichs so gemacht:
 int* array;
array=(int*) alloc(p*k,int)

Aber dann hab ich einfach ein eindimensionales Array mit k*p Einträgen, 
oder?

Wäre super, wenn mir da jemand weitrhelfen könnte!

Vielen Dank!

[Karl H. (kbuchegg)]

Martin Sche. schrieb:

> Aber dann hab ich einfach ein eindimensionales Array mit k*p Einträgen,
> oder?

Im Computer ist alles einfach nur eine Abfolge von Bytes.
Auch ein 2-dimensionales int Array ist nur eine Abfolge von int im 
Speicher. 2-dimensional wird es erst dadurch, dass die beiden Indizes 
mit einer Formel miteinander verknüpft werden um so die Indexnummer ab 
Beginn der ganzen Geschichte zu ermitteln.

Vielleicht kannst du die Formel ja ermitteln. Dazu malen wir einfach mal 
ein 2 dimensionales Array auf und schreiben in jedes Feld die 1-D 
Indexnummer des int, relativ zum Anfang des Ganzen.



       0   1   2   3   4

     +---+---+---+---+---+
  0  | 0 | 1 | 2 | 3 | 4 |
     +---+---+---+---+---+
  1  | 5 | 6 | 7 | 8 | 9 |
     +---+---+---+---+---+
  2  |10 |11 |12 |13 |14 |
     +---+---+---+---+---+

Das also ist dein 2D Array mit 5 Spalten und 3 Zeilen. Im Speicher liegt 
es so.

     +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
     | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 |14 |
     +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Wenn du also das Feld mit den 2-d Koordinaten Zeile:1/Spalte:3 suchst, 
dann brauchst du das Feld 8. Das 2-d Feld 2/1 ist an Position 11 zu 
finden, etc.

Frage: Wie muss die Formel aussehen, die die Umrechnung 2-D auf 1-D 
macht?

[Frank M. (ukw) (Moderator)]

Karl heinz Buchegger schrieb:

>> Aber dann hab ich einfach ein eindimensionales Array mit k*p Einträgen,
>> oder?
> Im Computer ist alles einfach nur eine Abfolge von Bytes.

Prinzipiell hast Du ja recht, aber eigentlich macht man das anders, als 
Du es andeutest, um ein mehrdimensionales Array zu allokieren.

Nämlich so:

#include <stdlib.h>

main ()
{
  int p = 5;              // Nur als Beispiel
  int k = 7;              // dito
  int ** array;           // Achtung: Doppelsternchen, da zweidimensional!
  int idx;

  array = malloc (p * sizeof (int *));  // allokiere p Pointer

  for (idx = 0; idx < p; idx++)
  {
      array[idx] = malloc (k * sizeof (int));
  }
}

Das heisst: Man muss zunächst p Pointer allokieren, denen man im zweiten 
Schritt jeweils ein _ein_dimensionales Array durch weiterere Allokation 
zuweist.

Dann kann man mit der Schreibweise array[x][y] genauso auf das Array 
zugreifen wie auf ein statisch definiertes Array mit festen Größen P und 
K. Klimmzüge (wie Formeln), um auf ein Element des Arrays zuzugreifen, 
sind dann gar nicht erst notwendig.

Gruß,

Frank

[Karl H. (kbuchegg)]

Frank M. schrieb:
> Karl heinz Buchegger schrieb:
>
>>> Aber dann hab ich einfach ein eindimensionales Array mit k*p Einträgen,
>>> oder?
>> Im Computer ist alles einfach nur eine Abfolge von Bytes.
>
> Prinzipiell hast Du ja recht, aber eigentlich macht man das anders, als
> Du es andeutest, um ein mehrdimensionales Array zu allokieren.

Das kommt drauf an.
Wenn das Array voll besetzt ist, macht man das schon so.
Wenn die einzelnen Zeilen unterschiedliche Länge haben, macht man es auf 
die von dir gezeigte Art. Denn du verbrauchst prinzipiell mehr Speicher 
:-) Wenn das mehrdimensionale Array sehr groß wird, macht man es auf die 
von dir beschriebene Art, denn dann kann einem Speicherfragmentierung 
nicht so leicht einen Strich durch die Rechnung machen.

> Das heisst: Man muss zunächst p Pointer allokieren, denen man im zweiten
> Schritt jeweils ein _ein_dimensionales Array durch weiterere Allokation
> zuweist.

Streng genommen, ist das dann in Summe kein 2D-Array mehr im C-Sinne, 
sondern ein Array von Pointern. Die interne Darstellung ist eine völlig 
andere als bei dem was der C Compiler unter einem 2D Array versteht :-). 
Lediglich durch die clevere Art und Weise, wie Array-Indizierung in C 
definiert ist, geht es, dass für beide Versionen beim Zugriff dieselbe 
Syntax benutzt werden kann.


> Dann kann man mit der Schreibweise array[x][y] genauso auf das Array
> zugreifen wie auf ein statisch definiertes Array mit festen Größen P und
> K. Klimmzüge (wie Formeln), um auf ein Element des Arrays zuzugreifen,
> sind dann gar nicht erst notwendig.

Was nicht unbedingt heißt, das das dann schneller geht :-)

Ob du bei einem echten 2D Array   [x][y]  schreibst, und der Compiler 
erzeugt Code für die eigentliche Indexberechnung, oder ob du das selber 
aufdröselst (weil das Array dynamisch allokiert werden muss), spielt 
laufzeitmässig keine Rolle :-)

Und ausserdem schadet es nicht, wenn man weiß, wie ein echtes 2D Array 
tatsächlich funktioniert und ein wenig nachdenken muss :-)

[Frank M. (ukw) (Moderator)]

Karl heinz Buchegger schrieb:

> Wenn die einzelnen Zeilen unterschiedliche Länge haben, macht man es auf
> die von dir gezeigte Art. Denn du verbrauchst prinzipiell mehr Speicher

Stimmt, ich "verbrauche" zusätzlich die Pointer.

> Streng genommen, ist das dann in Summe kein 2D-Array mehr im C-Sinne,
> sondern ein Array von Pointern. Die interne Darstellung ist eine völlig
> andere als bei dem was der C Compiler unter einem 2D Array versteht :-).

Richtig, praktisch ist aber der Zugriff über die gewohnte Schreibweise 
"array[x][y]" :-)

> Was nicht unbedingt heißt, das das dann schneller geht :-)

Hm, was zu überprüfen wäre. Du benötigst eine zusätzliche 
Multiplikation, ich einen indirekten Zugriff über Pointer.

Ich habe das mal mit dem AVR-GCC getestet und habe den Array-Zugriff in 
2 Funktionen gepackt, um Optimierungen des Compilers (Wissen über die 
Werte von x, y, k) auszuschließen:

int
value_of_1 (int ** a, int x, int y)     // meine Version
{
  return a[x][y];
}

int k = 7;

int
value_of_2 (int * a, int x, int y)     // Deine Version
{
  return a[k*x + y];
}

Der produzierte Assembler-Code (test.lss) sieht folgendermaßen aus:

int
value_of_1 (int ** a, int x, int y)
{
  76:  fb 01         movw  r30, r22
  78:  ee 0f         add  r30, r30
  7a:  ff 1f         adc  r31, r31
  7c:  e8 0f         add  r30, r24
  7e:  f9 1f         adc  r31, r25
  80:  44 0f         add  r20, r20
  82:  55 1f         adc  r21, r21
  84:  01 90         ld  r0, Z+
  86:  f0 81         ld  r31, Z
  88:  e0 2d         mov  r30, r0
  8a:  e4 0f         add  r30, r20
  8c:  f5 1f         adc  r31, r21
  return a[x][y];
}
  8e:  80 81         ld  r24, Z
  90:  91 81         ldd  r25, Z+1  ; 0x01
  92:  08 95         ret

00000094 <value_of_2>:

int k = 7;

int
value_of_2 (int * a, int x, int y)
{
  94:  fc 01         movw  r30, r24
  96:  cb 01         movw  r24, r22
  98:  9a 01         movw  r18, r20
  9a:  60 91 60 00   lds  r22, 0x0060
  9e:  70 91 61 00   lds  r23, 0x0061
  a2:  86 d1         rcall  .+780      ; 0x3b0 <__mulhi3>
  a4:  28 0f         add  r18, r24
  a6:  39 1f         adc  r19, r25
  a8:  22 0f         add  r18, r18
  aa:  33 1f         adc  r19, r19
  ac:  e2 0f         add  r30, r18
  ae:  f3 1f         adc  r31, r19
  return a[k*x + y];
}
  b0:  80 81         ld  r24, Z
  b2:  91 81         ldd  r25, Z+1  ; 0x01
  b4:  08 95         ret

Die Anzahl der Instruktionen sieht erstmal gleich aus, aber bei näherem 
Hinsehen fällt bei Deiner Version der rcall von _mulhi3 auf, der noch 
einiges an zusätzlichem Code kostet:

000003b0 <__mulhi3>:
 3b0:  55 27         eor  r21, r21
 3b2:  00 24         eor  r0, r0

000003b4 <__mulhi3_loop>:
 3b4:  80 ff         sbrs  r24, 0
 3b6:  02 c0         rjmp  .+4        ; 0x3bc <__mulhi3_skip1>
 3b8:  06 0e         add  r0, r22
 3ba:  57 1f         adc  r21, r23

000003bc <__mulhi3_skip1>:
 3bc:  66 0f         add  r22, r22
 3be:  77 1f         adc  r23, r23
 3c0:  61 15         cp  r22, r1
 3c2:  71 05         cpc  r23, r1
 3c4:  21 f0         breq  .+8        ; 0x3ce <__mulhi3_exit>
 3c6:  96 95         lsr  r25
 3c8:  87 95         ror  r24
 3ca:  00 97         sbiw  r24, 0x00  ; 0
 3cc:  99 f7         brne  .-26       ; 0x3b4 <__mulhi3_loop>

000003ce <__mulhi3_exit>:
 3ce:  95 2f         mov  r25, r21
 3d0:  80 2d         mov  r24, r0
 3d2:  08 95         ret

Damit nehme ich mal ein, dass meine Version mehr als doppelt so schnell 
auf ein 2-dimensionales Array zugreifen kann - jedenfalls bei AVR-µCs. 
Das kann natürlich bei Prozessoren, für die eine int-Multiplikation ein 
Klacks ist, ganz anders aussehen.

> Und ausserdem schadet es nicht, wenn man weiß, wie ein echtes 2D Array
> tatsächlich funktioniert und ein wenig nachdenken muss :-)

Da hast Du natürlich vollkommen recht :-)

Gruß,

Frank

[Jörg W. (dl8dtl) (Moderator)]

Frank M. schrieb:

> Richtig, praktisch ist aber der Zugriff über die gewohnte Schreibweise
> "array[x][y]" :-)

Das geht auch bei linearer Anordnung:

int
value_of_3 (int a[][5], int x, int y)
{
  return a[x][y];
}

Braucht allerdings auch eine Mulitiplikation, sofern nicht die
letzte Dimension eine Zweierpotenz ist.

Letztlich ist der Funktion egal, ob der Aufrufer den Speicherplatz
als (echtes) zweidimensionales Array oder via malloc() gewonnen hat.

[Frank M. (ukw) (Moderator)]

Jörg Wunsch schrieb:

> Das geht auch bei linearer Anordnung:
>
>

> int
> value_of_3 (int a[][5], int x, int y)
> {
>   return a[x][y];
> }
>

Stimmt.

> Braucht allerdings auch eine Mulitiplikation, sofern nicht die
> letzte Dimension eine Zweierpotenz ist.

Ja. Und die Funktion muss zusätzlich eine Dimension des Arrays kennen. 
Wenn aber beide Dimensionen dynamisch sind, scheidet diese Variante aus.

Gruß,

Frank

[Jörg W. (dl8dtl) (Moderator)]

Frank M. schrieb:

> Ja. Und die Funktion muss zusätzlich eine Dimension des Arrays kennen.
> Wenn aber beide Dimensionen dynamisch sind, scheidet diese Variante aus.

Nein, dann nehmen wir ein C99 variable-length array. :-)

int
value_of_3 (int x, int y, int n, int m, int a[n][m])
{
  return a[x][y];
}

[Frank M. (ukw) (Moderator)]

Jörg Wunsch schrieb:

> Nein, dann nehmen wir ein C99 variable-length array. :-)

Nett, kommt aber auch nicht um die Plutimikation herum :-)

[Jörg W. (dl8dtl) (Moderator)]

Frank M. schrieb:

> Nett, kommt aber auch nicht um die Plutimikation herum :-)

Logisch, aber die würde auch das originale zweidimensionale Array
halt machen, wenn man es statisch im Compiler anlegt (sofern nicht
die zweite Dimension 2^N ist).

Ich wollte ja auch keinesfalls bestreiten, dass der Vektor aus Zeigern
seine Vorteile hat; die hat er vor allem dann, wenn die Länge der
einzelnen Elemente nicht konstant ist (Vektor aus Zeigern, die auf
Zeichenkettenkonstanten zeigen zum Bleistift).

[Klaus W. (mfgkw)]

geht es hier eigentlich um C auf einem MC oder um etwas größeres?