C pointer auf mehrdimensionales Array (Matrizen)

[Heng]

Hi, bin noch ziemlicher C-Anfänger.
Habe ein Programm geschrieben um Matrizen zu multiplizieren.
Ab einer bestimmten Matrixgröße bekomme ich Speicherzugriffsprobleme, ich denke es liegt daran, dass ich nicht mit Pointern gearbeitet habe.
Ich weiß jetzt nicht wie ich das bei zweidimensionalen Array anstellen soll.

Danke schonmal

 

[KingofKingzZ]

Ein dynamischen 2Dimensionales Array kannst du so erstellen:

int i** = new Part*[Width];
for (int c = 0; c < Width; ++c)
i[c] = new Part[Height];

Darauf zugreifen kannst du dann ganz normal also i[x][y];

Deleten geht dann so:

for (int j = 0; j < Width ; j++)
delete [] i[j] ;
delete [] i;


Allerdings liegt der Fehler bei dir wohl eher daran, dass du über das Array herausschreibst oder liest, denn wenn du Zeiger verwendest würden solche Fehler auch nicht weggehen, die Größe ist ja immer noch vorgegeben.

lg chaia


Edit: Ups, hier gehts ja um C, dann musst du den Speicher mit malloc reservieren.

 

[Sheeep]

Hi,
entweder so:
int m = 30;
int n = 20;

float **matrix = (float**) malloc(sizeof(float*) * m);
int i = 0;
for(i=0; i < m; i++)
{
matrix = (float*) malloc(sizeof(float) * n);
}

oder du nimmst ein eindimensionales array und greifst mit
matrix[i * n + j]
drauf zu, wobei i die zeilen und j die spaltenkoordinate und n die anzahl der spalten ist.

MFG Sheeep

@KingofKingzZ
new geht nur in c++, delete genauso, in c brauchst du malloc() und free();
@Heng
wenn du einen c++ compiler verwendest, ist es einfacher, wenn du es so machst, wie KingofKingzZ gesagt hat.

 

[Heng]

Danke, das werde ich Morgen mal ausprobieren.

Ich benutzte den gcc compiler von linux (ubuntu)

 

[Sheeep]

der gcc unterstützt kein new oder delete, da der ein reiner c compiler ist,
du musst malloc einsetzen.

MFG Sheeep

 

[Heng]

Sollte ich denn lieber mit ein- oder zweidimensionalen Arrays arbeiten?
Wie sähe das denn z.B. bei diesem Programm aus.

 

[bingo88]

Eindimensionale Arrays haben den Vorteil, dass sie am Stück im Speicher liegen, also als ein großer Block. Das vereinfacht es natürlich dem CPU Cache, Speicherzugriffe zu cachen und Vorhersagen zu treffen. Nachteil ist allerdings, dass du wirklich genug Speicher frei haben musst, um einen entsprechend großen Block anlegen zu können.

Bei zweidimensionalen Arrays der Form **double, wo jedes Element ein Zeiger auf eine Spalte oder Zeile der Matrix enthält, sieht die Sache erheblich anders aus. Du hast nämlich jetzt nicht notwendigerweise die einzelnen Zeilen bzw. Spalten der Matrix als Block im Speicher, sondern das kann durchaus hässlich fragmentiert sein. D. h. Speicherzugriffe sind u. U. nicht so performant wie bei einem eindimensionalen Array.

Grundsätzlich wird Speicher immer als eindimensionales Array angefordert, schließlich ist Speicher in einem linearen Adressraum organisiert. Daher wird eine Anweisung double matrix[5][5] z. B. in double matrix[5 * 5] übersetzt. Der Zugriff der Form a[1][2] klappt in C nur, wenn die Anzahl der Spalten pro Zeile bereits zur Compile-Zeit bekannt war, da dieser Aufruf in a[1 + 2 * anzSpalten] übersetzt wird.

 

[Heng]

Ich bekomme das leider mit den Pointern noch nicht hin.
Mein Programm soll einfach die Matrizen A x A = C multiplizieren.

Wie besetzt man dann die Matrizen bei pointern?
Am besten wäre ein kleines Beispiel.

Danke

 

[bingo88]

const int anzZeilen = 5;
const int anzSpalten = 5;
double *matA = new double[anzZeilen * anzSpalten]; // 5 x 5 Matrix
for (int zeile = 0; zeile < anzZeilen; ++zeile)
{
    for (int spalte = 0; spalte < anzSpalten; ++spalte)
    {
        matA[zeile * anzSpalten + spalte] = 0.0; // initialisiere mit 0
    }
}

Die Matrix liegt so im Speicher:

matA = [0 1 2 3 4; 0 1 2 3 4; 0 1 2 3 4; 0 1 2 3 4; 0 1 2 3 4]
Zeile:   1 (0)       2 (1)       3 (2)      4 (3)       5 (4)       (Klammer enthält index)

von daher musst du für die Operation matA[2][3] (die so nicht geht!!!) soetwas schreiben:
matA[2 * anzSpalten + 3]

 

[Bauer87]

Wenn die Zeilen- und Spaltenanzahl eh fest ist, tut es ein einfaches „int A[5][5]“, wie du es gemacht hast. Da muss man dann nichts mehr allozieren (weder C-Syle mit malloc, noch C++-Style mit new). Und es sind automatisch Pointer. Wenn du Probleme bekommst, „int A[64][64]“ (also ne 64x64-Matrix) statisch zu allozieren, wird das auch bei dynamischer Speicherbelegung passieren. Wenn du also nicht vor hast, Matrizen unterschiedlicher, dynamischer Größe zu unterstützen, brauchst du dich nicht darum zu kümmern. (Unten Rechts ne Einheitsmatrix anzuhängen, den Rest mit Nullen zu befüllen und intern mit größeren Matrizen zu rechen kostet einfach zu viel Rechenleistung.)

PS: Code als Bilddatei ist ja mal ne üble Idee.

 

[Heng]

Hmm wo liegt denn der Fehler?
Hab im Anhang mal den Code ind die kompilierten Programme.

Bei einer 500x500 Matrix bekomme ich keine Probleme, die wird noch ausgerechnet.
Aber bei 800x800 Sagt er mir Speicherzugriffsfehler.

Liegt das nicht daran, das ich nicht mit pointern arbeite?

 

[Zappzarrap]

Wieso deklarierst du int main (void) und gibst 0 zurück? Das macht irgendwie
keinen Sinn...

Zum Code posten empfehlen sich seiten wie pastebin oder nopaste, dann
muss sich nicht jeder deinen Code runterladen und es sieht trotzdem gut
aus...

Ohne mir dein Programm näher angesschaut zu haben tippe ich mal darauf
das dein Stack vollläuft. Übrigens kannst du mit gdb in der Konsole debuggen.

RMS's gdb Tutorial: Segmentation Fault Example

Hier steht wie du in variablen reinschauen kannst, obwohl dein programm
schon abgestürzt ist...

 

[Heng]

Danke für die Antworten,

scheinbar ist der Stack übergelaufen.
Habe den Stack mit

ulimit -s 48000

vergrößert.
Nun kann ich schon wesentlich größere Matrizen berechnen.
Bei einer bestimmten größe bekomme ich aber wieder Probleme, da man den Stack nich beliebig vergrößern kann oder?

Woran liegt das, dass der Stack überläuft und wie kann man das verhindern?

Gruß

 

[bingo88]

Deswegen legt man große Matrizen ja auch nicht im Stack sondern im Heap (also mit malloc etc.) an.

Einen Stacküberlauf kannst du nur verhindern, in dem du den Stack nicht so ausgiebig nutzt. Im gegensatz zu Adressen im Heap "wächst" der Stack übrigens auch nach unten, d.h. die Speicheradressen werden immer kleiner, je mehr Elemente im Stack enthalten sind.

Wenn du in deinem Code eine Variable deklarierst, z. B. so

void func() {
    int a = 0;
    ...
}

dann erzeugt der Compiler daraus bspw. folgenden Maschinencode:

func:
    push ebp ; alten Basepointer sichern
    mov ebp, esp ; alten Stackpointer sichern
    sub esp, 4 ; mache Platz für einen Int (4 Byte) auf dem Stack
    mov DWORD PTR [ebp - 4], 0 ; a = 0
    ...
    mov esp, ebp ; Stackpointer wiederherstellen
    pop ebp ; Basepointer wiederherstellen
    ret ; Funktion verlassen

Die interessante Stelle ist nun "sub esp, 4". Da wird der Stackpointer um 4 Bytes (also ein int) verkleinert. Dies bedeutet aber, es wird Platz für einen Int geschaffen, der SP wird also kleiner! Wenn du jetzt große Variablen hast (Matrix 800 x 800 x 8 Byte = 5MB) ist dieser Speicher zu klein und du bekommst einen Fehler.

Du musst bedenken, jeder Funktionsaufruf (zumindest die, die nicht inline erfolgen) benötigt ebenfalls Platz auf dem Stack. Außerdem werden die meisten Funktionsargumente ebenfalls im Stack abgelegt.

Von daher solltest du große Variablen bzw. Datenstrukturen besser nicht im Stack anlegen

 

[Heng]

Ok, also bei großen Arrays besser mit malloc arbeiten?
Sagen wir mal der Stack reicht....
Gibt es da Performanceunterschide ob man den Stack oder Heap benutzt.
Bin noch ziemlicher Anfänger.

Danke und Gruß

 

[bingo88]

Du hast bei Stackbasierten Variablen halt keine Initialisierungskosten durch malloc/new Aufrufe, da Stackvariablen zur Compile-Zeit bekannt sein müssen (also die Größe). Das ist auch der Grund, warum double m[n * n]; nicht funktioniert, außer n ist ein #define oder eine Konstante.

Der Stack liegt normalerweise auch im normalen Arbeitspeicher, von daher sind die Zugriffskosten vergleichbar. Ein Nachteil von stackbasierten Variablen ist außerdem, dass du keinen Zeiger auf eine innerhalb einer Funktion deklarierte non-static Variable nach außen dringen lassen kannst:

float *getArray() {
    float array[10];
    return &array; // Kompiliert zwar aber ist böse! Ganz böse sogar
}

Das wäre allerdings möglich, wobei es auch hier Nachteile bzw. Schwachstellen gibt:

float *getArray() {
    float *array = new float[10];
    return array; // kann man zwar machen, ist aber nicht unbedingt guter Stil, von der Fehlersicherheit mal ganz zu schweigen...
}

 

[Heng]

Alles klar, ich hoffe das wars erstmal.
Falls nicht melde ich mich nächste Woche nochmal.
Hoffe du hast das Thema abonniert.

Schönes Wochenende noch!

Gruß

 

[bingo88]

Alles klar, ich hoffe das wars erstmal.
Falls nicht melde ich mich nächste Woche nochmal.
Hoffe du hast das Thema abonniert.

Schönes Wochenende noch!

Gruß

Ja, ich bin eigentlich nur noch in der Programmier-Sektion unterwegs

Ebenso ein schönes Restwochenende!

 

[Zappzarrap]

Ja, ich bin eigentlich nur noch in der Programmier-Sektion unterwegs !

Hehe, dito in den anderen Bereichen verliert man zu schnell den Überblick was
finde ich