Discussion :

[chalulu]

Bonjour à tous,

J'écris un programme en C++ pour un élève. Cela consiste à programmer un automate cellulaire qui mime la propagation d'un feu. En gros on a un gros tableau qu'on fait évoluer selon la règle suivante : si une cellule du tableau brûle au temps t, elle contamine ses voisines avec la probabilité p. J'ai besoin de conserver tous les temps intermédiaires afin qu'il puisse analyser la dynamique de propagation. J'ai écris le code suivant, qui fonctionne pour de petits tableaux (50x50) mais pas pour des gros (stack overflow)...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
#include <iostream>
#include <cmath>
#include <vector>
#include <array>
#include <cstdlib>
 
using namespace std;
 
const int N = 501;
 
class Cell{
	int state;
	int burning;
	public:
		void sets(int s){
			state = s;
		}
		int gets(){
			return state;
		}
		void setburning(int b){
			burning = b;
		}
		int getburning(){
			return burning;
		}
		Cell(){
			state = 0;
			burning = 0;
		}
		Cell(int s, int b){
			state = s;
			burning = b;
		}
		Cell operator= (Cell C){
			int s = C.gets();
			int b = C.getburning();
			return Cell(s,b);
		}
};
 
typedef  array<array<Cell,N+2>,N+2> Cells;
 
int BurningNeighbors(Cells CA, int i, int j){
	int Burn;
	Burn = CA[i+1][j-1].getburning()+CA[i+1][j].getburning()+CA[i+1][j+1].getburning()+
		CA[i][j-1].getburning()+CA[i][j+1].getburning()+CA[i-1][j-1].getburning()
		+CA[i-1][j].getburning()+CA[i-1][j+1].getburning();
	return Burn;
}
 
Cells evol(Cells CA, double p){
	Cells CA2 = CA;
	for (int i = 1; i < N+1; i++){
		for (int j = 1; j < N+1; j++){
			if (CA[i][j].gets() == 1){
				CA2[i][j].sets(2);
			}
			else if (CA[i][j].gets() == 2){
				CA2[i][j].sets(3);
				CA2[i][j].setburning(0);
			}
			else if (CA[i][j].gets() == 0) {				
				int Burn = BurningNeighbors(CA,i,j);
				if (Burn > 0){		
					double Guess = (double) (rand() % 1000)/1000.;
					if (Guess < 1-pow(1-p,Burn)) {
						//cout << "Guess: " << Guess << "; 1-(1-p)^Burn: " << 1-pow(1-p,Burn) << endl;
						CA2[i][j].sets(1);
						CA2[i][j].setburning(1);
					}
				}
			}
		}
	}	
	return CA2;
}
 
int isBurning(Cells CA){
	for (int i = 1; i < N+1; i++){
		for (int j = 1; j < N+1; j++){
			if (CA[i][j].getburning() == 1){
				return 1;
			}
		}
	}
	return 0;
}
 
int main()
{
	// Creation of Cells vector
 
	cerr << "Beginning " << endl;
 
	double P = 0.2;
 
	vector<Cells> *CAs = new vector<Cells>();
 
	// Initialisation
	cout << endl << "Initialisation" << endl << endl;
 
	static Cells CA;
 
	for (int j = 0; j < N+2; j++){
		CA[0][j].sets(3);
		CA[N+1][j].sets(3);
	}
	for (int i = 0; i < N+2; i++){
		CA[i][0].sets(3);
		CA[i][N+1].sets(3);
	}
	CA[floor(N/2)+1][floor(N/2)+1].sets(1); 
	CA[floor(N/2)+1][floor(N/2)+1].setburning(1); 	
	CAs->push_back(CA);
	int T = 0;
	while (isBurning(CAs->at(CAs->size()-1))){
		T++;
		cout << endl << "time step:" << T << endl << endl;
		CAs->push_back(evol(CAs->at(CAs->size()-1),P));
	}
 
	return 0; 
}

Je pense que le problème se situe dans la déclaration de CAs (qui contient l'état du tableau pour chaque pas de temps), mais je n'en suis pas certain, j'ai donc mis une version simplifiée du code.

N est la taille du tableau de cellules;
P est la probabilité que le feu soit transmis d'une cellule à une de ses voisines;
evol est la fonction qui prend le tableau au temps t et rend le tableau au temps t+1;
isBurning rend 1 s'il y a des cellules qui brûlent dans le tableau, 0 sinon;
BurningNeighbors calcule le nombre de voisins d'une cellule qui brûlent, la fonction étant appelée par evol;
CAs contient tous les états du tableau, de son initialisation à l'extinction du feu.

La question est probablement triviale pour un habitué du C++, soyez indulgents s'il vous plaît je n'ai commencé ce langage que très récemment

[ternel]

Chaque Cells 503 * 503 * {2 ints}, que ca correspond a priori à 250000 * 8 octets soit 2 Mo, ce qui est déjà énorme.

Ca ne peut pas marcher, a cause des fonctions:
Cells evol(Cells CA, double p) reçoit une copie de son arguments lorsqu'elle est appelée. Et cette copie est faite dans la pile.


Passe par des références.
evol(Cells const& CA, double p)

Mieux crée une classe Simulation adaptée (regarde la faq sur les matrices: pourquoi et comment)

[chalulu]

Tout d'abord, merci pour ton aide

J'ai modifié evol de la manière que tu m'as conseillée, j'ai eu cette erreur à la compilation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
CA_so.cpp: In function 'Cells evol(const Cells&, double)':
CA_so.cpp:57:22: error: passing 'const value_type {aka const Cell}' as 'this' argument of 'int Cell::gets()' discards qualifiers [-fpermissive]
    if (CA[i][j].gets() == 1){
                      ^
CA_so.cpp:60:27: error: passing 'const value_type {aka const Cell}' as 'this' argument of 'int Cell::gets()' discards qualifiers [-fpermissive]
    else if (CA[i][j].gets() == 2){
                           ^
CA_so.cpp:64:27: error: passing 'const value_type {aka const Cell}' as 'this' argument of 'int Cell::gets()' discards qualifiers [-fpermissive]
    else if (CA[i][j].gets() == 0) {

Je pense qu'il faut modifier gets() et getburning() dans la classe Cell, donc j'ai modifié le code ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
int gets() const{
			return state;
		}
int getburning() const{
			return burning;
		}

J'avoue, avec un grand desarroi, avoir rajouté des const un peu partout jusqu'à compilation ^^'. Je pense que mettre un const à cet endroit spécifie au compilateur que ni state ni burning ne seront modifiés par les fonctions gets() et geotburning().

J'ai rajouté des const& à BurningNeighbors et isBurning pour éviter la même erreur que tout à l'heure, j'ai maintenant une nouvelle erreur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
time step:255
 
 
time step:256
 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
 
This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

Une idée ?

Bon appétit :=)

[Médinoc]

Cette erreur, c'est le "out of memory" du tas. En gros, un new qui n'arrive pas à allouer ton un objet. Je pense que c'est dû à ton vecteur de Cells, qui a besoin de faire des allocations de "N*2MO consécutifs" quand il s'agrandit... Essaie plutôt avec une std::list, qui devrait allouer objet par objet.

Edit: Regarde aussi si tu ne peux pas écrire tous ces temps dans des fichiers pour libérer la RAM.

[chalulu]

C'est étrange, j'ai 32Go de RAM, normalement ça devrait passer non ? 256*2Mo ce n'est pas si grand...
Je vais essayer avec une list, je vous dirai.

[Médinoc]

Quel OS?
La plupart des compilos sous Windows sont encore en "32 bits par défaut", donc à moins de compiler ton programme pour x64, tu seras limité à 2GO d'espace d'adressage par processus.
J'ignore s'il y a ce genre de limitations sous les unixoïdes 64 bits.