Speicherzugriffsfehler bei zu großem Array

Hi!

Ok, ich muss vorausschicken, dass ich C-Anfänger bin und ich hab ein kleines Problem, wofür ich bis jetzt im Netzt keine Lösung gefunden habe.
Es geht um ein C-Programm, das ich geschrieben habe, das einen physikalisches Modell simuliert. Dabei wird ein Baum von oben nach unten erzeugt mit einer maximalen Tiefe von tmax. Auf obersten Ebene gibt es einen Platz, in der zweiten 2, in der dritten 3... in der tmax-ten tmax Plätze:

t=0      -
t=1     - -
t=3    - - -
t=4   - - - -
t=5  - - - - -
usw...

Der Platz in der obersten Ebene ist belegt. In jeder folgenden Ebene kann nur dann ein Platz belegt werden, wenn der Platz links oder rechts über ihm belegt ist. Ist das der Fall entscheidet ein Zufallsgenerator anhand eine Wahrscheinlichkeit p ob auch dieser Platz belegt wird. Nachdem eine Ebene fertig ist, werden die Anzahl n der belegten Plätze gepeichert.

Es werden nun viele (genaue Anzahl: rlmax) solcher Zufallsbäume erzeugt und für jede Ebene ein Mittelwert (arithmetisch) aus den Werten aller Bäume, die in dieser Ebene noch "aktiv" sind (können ja auch schon vor Erreichen von tmax ausgestorben sein), berechnet.

So, nun zu meinem Problem: Dieses Programm soll mit sehr vielen Bäumen und einer sehr hohen "Ebenentiefe" rechnen. Wenn ich aber ein Array mit zuvielen Feldern benutze, dann bekomme ich einen Speicherzugriffsfehler in der Ausgabe. Hat da jemand eine Ahnung woran das liegt?

Eine zweite Frage wäre, wie man denn anstelle des arithmetischen Mittels das geometrische Mittel umsetzt, dabei werden alle Werte aufmulipliziert und dann die n-te Wurzel gezogen, wobei n die Anzahl der Elemente ist?

Hier mein Code:

/* Simulationsprogramm zur 'Directed Percolation' - Version 0.8 - Benedikt Vormwald - bvormwald@antesilvam.de -
07/2005*/

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <gsl/gsl_rng.h>

long tmax=10000000;   //maximale Tiefe des Baums
long rlmax=1000;      //Anzahl der Wiederholungen
float p=0.6833;       //Wahrscheinlichkeit

int main()
{
  int rl, t, s, n, fsiteset, fsite, lsite, actfsite,  actlsite, l, m, k;
  double z;

  const gsl_rng_type * T;
  gsl_rng * r;

  int site[tmax][tmax];     //"Platzverzeichnis"
  int values[tmax][rlmax];  //"Werteverzeichnis"

  for(l=0; l<tmax; l++)    //Initialisierung der Arrays mit 0
  {for(m=0; m<tmax; m++) { site[l][m]=0; } for(k=0;k<rlmax; k++){ values[l][k]=0;}}

  gsl_rng_env_setup();    //Einlesen der Zufallsgenerator-Umgebungsvariablen
  T = gsl_rng_default;    //Initialisierung des Zufallsgenerators
  r = gsl_rng_alloc (T);  //Initialisierung des Zufallsgenerators

//Baumerzeugung------------------------------------------

  for(rl=0; rl<rlmax; rl++) //Anzahl der verschiedenen Realisierungen/ Anzahl der verschiedenen Bäume
  {
    for(t=0; t<tmax; t++)  //Zeitebene/ Tiefe des Baums
    {
      if(t==0){fsite=0; lsite=0;}
      n=0;
      actfsite=fsite;
      actlsite=lsite;
      fsiteset=0;
      for(s=actfsite; s<=(actlsite+1); s++)  //Plätze in der Ebene -> An den Rändern können evt. gespart werden´.
      {
        z = gsl_rng_uniform_pos (r);  //Generierung einer Zufallszahl/
        if ((t==0)||((z<=p)&&((site[t-1][s]==1)||(site[t-1][s-1]==1))))  //Bedinunge für einen aktiven Platz
        {
          site[t][s]=1;  //Ein aktiver Platz wird im "Platzverzeichnis" eingetragen
          n=n+1;         //Die Anzahl der aktiven Plätze pro Ebene wird um eins erhöht
          lsite=s;       //Für die nächste Ebene der lezte aktive Platz gemerkt --> s.o. hier kann gespart werden.
          if(fsiteset==0){fsite=s; fsiteset=1;}  //Der erste aktive Platz der Ebene wird gespeichert.
        }
       }
      values[t][rl]=n;  //in diesem Array werden die aktiven Plätze pro Ebene gespeicher, sortiert nach der Zeit
      if(fsiteset==0){break;}  //Wenn kein aktiver Platz in der Ebene vorhanden ist, wird der Baum abgebrochen
    }
  }
  gsl_rng_free (r);  //Der vom Zufallsgenerator belegte Speicher wird geräumt

//Mittelwertsberechnung(arithmetisch)-------------------------------------------

  int sum=0;
  int elements=0;
  float average[tmax];

  for(t=0; t<tmax; t++)    //Auslesen des "Werteverzeichnis" nach dem den Ebenen sortiert
  {
    for(rl=0; rl<rlmax; rl++)
    {
      if(values[t][rl]!=0)  //Falls der Wert nicht Null ist, wird er zur Mittelwertsberechnung herangezogen
      {
        sum=sum+values[t][rl];  //Die Werte werden aufaddiert
        elements=elements+1;    //Die Anzahl der "relevanten" Werte wird bestimmt
      }
    }
    average[t]=((float)sum/(float)elements);      //Aus den Ergebnissen wird der Mittelwert gebildet
    printf("x: %d\ty: %g\n", (t+1), average[t]);  //und am Bildschirm ausgegeben
    elements=0;  //Null setzen für den nächsten Durchlauf
    sum=0;       //Nullsetzen für den nächsten Durchlauf
  }
  printf("\n");
  return(0);
}

Wäre schön, wenn ihr mir helfen könntet. Mit den Werten tmax=1000 und rlmax=1000 liefert das Programm jedenfalls einwandfreie Ergebnisse. nur beie höheren Werten gibts die Probleme.

Danke schonma im Voraus

Noch ein kleiner Nachtrag: Wenn ich bei den Kommentaren ab und zu von Zeit rede, sind damit die Ebenen gemeint. (Is nämlich im Modell das selbe)

int site[tmax][tmax];     //"Platzverzeichnis"

10 Mill. * 10 Mill. * 4 Byte (vermutlich, hängt vom Compiler ab) = 400 Billionen Byte. Hat Dein Rechner so viel RAM?

YASC

Joe_M. schrieb:

int site[tmax][tmax];     //"Platzverzeichnis"
10 Mill. * 10 Mill. * 4 Byte (vermutlich, hängt vom Compiler ab) = 400 Billionen Byte. Hat Dein Rechner so viel RAM?

Der Junge braucht ne große Festplatte zum Auslagern

Also die Werte bei dem der Zugriffsfehler kommt ist scho bei tmax=1000 und rlmax=10000. Das wären so ca. 9,5 mb Arbeitsspeicher für das eine Array (rl) und 0.95 mb für das andere Array(sites). Der Rechner hat aber 512 mb ram und dann nochmal soviel swap auslagerungsspeicher. Irgend ne andere idee? ^^###

Zu der anderen Frage: wie kann ich in C die n-te Wurzel aus einer Zahl ziehen?

Viele Grüße
Bene

MFK

Bene schrieb:

Der Rechner hat aber 512 mb ram und dann nochmal soviel swap auslagerungsspeicher. Irgend ne andere idee? ^^###

Du legst die Arrays auf dem Stack an. Der ist üblicherweise begrenzt. Du musst den Heap benutzen, Stichwort malloc. In den FAQ sollte genug über dynamische Speicherallokation stehen.

Zu der anderen Frage: wie kann ich in C die n-te Wurzel aus einer Zahl ziehen?

Mit der Funktion pow.

Ich bekomme aber kein Stack-Overflow, sondern einfach nur einen Speicherzugriffsfehler... Is das denn das gleiche?

Stackoverflow hat damit nichts zu tun. Die bekommst Du z.B. wenn Du in einer rekursiven Funktion die Abbruchbedingung vermurkst und dabei für jeden weiteren Aufruf der Funktion die Rücksprungadresse auf den Stack geschrieben wird.
Er meinte das automatische Variablen auf dem Stack allokiert werden und dynamische Variablen auf dem Heap. Aber selbst auf dem Heap kann es passieren, das nicht genug freier Speicher in einem zusammenhängenden Block verfügbar ist.

Aber eigentlich hatte ich einen bad alloc oder ähnliches erwartet (allerdings verwende ich einen C++-Compiler).

Grüße Joe_M.

Wie kann ich das dann umgehen? Ich bin wie gesagt relativer Neuling und hab mit diesem Speicherkram noch ned den vollen Durchblick. Es wäre für mich sehr wichtig mindestens 1000*10000 zu schaffen (tmax=1000 und rlmax=10000). Bin scho total verzweifelt. Das mit der dynamischen Methode versteh ich ned so ganz...

Und nur nochma damit ich mir sicher bin: Stack ist ein Speicherbereich, der für automatische Variablen verwendet wird und Heap einer für dynmische?

Ciao und danke, dass ihr mir alle so helft

c.rackwitz

int dx = 5, dy = 8, x, y;
int **array = malloc(sizeof(int*) * dy); // ein array von pointern
for (y = 0; y < dy; ++y) array[y] = malloc(sizeof(int)*dx);
/* Zugriff: array[y][x] */
for (y = 0; y < dy; ++y) free(array[y]); // das Freigeben des Speichers ist WICHTIG!
free(array);

Ich hab jetzt alles so gemacht, bekomm aber immernoch meinen Speicherzugriffsfehler...
Kann ma da garnix machen?

Viele Grüße, Bene

c.rackwitz

gib mal ein minimales programm, bei dem du diesen fehler reproduzieren kannst. also "hallo welt" mit crashroutine.

Hey! Es scheint jetzt zu funktionieren, vorhin hat er nur abgebrochen, weil ich das Proggie auf nem anderen Rechner über ssh kompilier und teste und mein Kumpel da den Prozess abgeschossen hat, weil er zu viel Ressourcen gefressen hat.

Aber ich hätte noch eine andere Frage... Beim geometrischen Mittel werden ja die einzelnen Werte aufmultipliziert und bei einem Mittel über 10000 oder mehr Werte ergibt sich da eine ziemlich große Zahl, die mit Sicherheit größer als 4294967295 ist. Wie kann ich mit einer so großen Zahl rechnen?

c.rackwitz

Bene schrieb:

bei einem Mittel über 10000 oder mehr Werte ergibt sich da eine ziemlich große Zahl, die mit Sicherheit größer als 4294967295 ist. Wie kann ich mit einer so großen Zahl rechnen?

typ double, ungenau aber der haelts aus.
oder such dir ne bigint library (gmp z.b.)

hab mal grad was getestet.
die zahlen 1-999 aufmultipliziert ergibt 4.024E2564. das schafft kein double.

ok, problem hat sich bei mir gelöst... Hab einen guten Tip bekommen... Die Werte werden im Anschluss ja noch logarithmiert, d.h. man kann auch jeden Wert logarihtmieren und die dann aufaddieren anstelle alle aufzumultiplizieren und dann erst log() anzuwenden... Es lebe die Mathematik XD