Fuite mémoire avec le HEAP et Priority Queue
Bonjour à toutes et à tous,
En préambule: je découvre le C++ et la priority_queue.
J'ai besoin de recoder un tout petit bout de programme (l'algorithme de dijkstra) afin de calculer des distances dans un graphe. Plus précisément, je teste un grand nombre de graphes de tailles différentes et ce petit bout de programme est appelé pour chaque graphe. Plus précisément la structure de mon programme ressemble à ceci:
Code:
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
| void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
/***********************************
*DECLARATIONS AND INITS
***********************************/
...
/*******************************
* Gather Inputs and Outputs & Alloc structures:
*******************************/
...
//Then perform the search for inflow and outflow nodes (find requested distance):
for(i=0; i < N; i++) {
for(j=0; j < N; j++) {
if(rand_idx[i] < j && rand_idx[i] != N-1) { //only read the upper triangular part and omit the last line.
const int cur_dis = dijkstra(rand_idx[i], j);
//mexPrintf("distance=%d\n", distance);
if(cur_dis >= distance) {
//assign outputs and returns:
//also correct for indexation between MATLAB & C
plhs[0] = mxCreateDoubleScalar(rand_idx[i] +1 ); //in
plhs[1] = mxCreateDoubleScalar(rand_idx[j] +1 ); //out
plhs[2] = mxCreateDoubleScalar(cur_dis); //fdistance
return;
}
}
}
}
//we browsed 'A' without finding the requested distance, thus assign '-1' to outputs
plhs[0] = mxCreateDoubleScalar(-1.0); //in
plhs[1] = mxCreateDoubleScalar(-1.0); //out
plhs[2] = mxCreateDoubleScalar(-1.0); //fdistance
} |
J'appelle donc la fonction dijkstra() un grand nombre de fois, et je retourne mon résultat 'plhs' à MATLAB. Cette fonction compilée est appelée un grand nombre de fois pour des graphes différents. L'algorithme fonctionne, les solutions sont correctes. La fonction dijkstra() utilise une priority_queue en global, avec des structures simples, c'est à dire:
Code:
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
| vector < vector <int> > graph;
vector < vector <int> > weight;
vector < int> cost;
int N;
struct cmp
{
bool operator()(const int &lhs, const int &rhs) const
{
return cost[lhs] > cost[rhs];
}
};
int min(const int a, const int b)
{
if(a<b)
return a;
return b;
}
priority_queue <int,vector<int>,cmp> pq;
int dijkstra(const int from, const int to)
{
vector <bool> visited(N, false);
visited[from] = true;
cost [from] = 0;
pq.push(from);
while(!pq.empty() && !visited[to])
{
int current = pq.top();
pq.pop();
visited[current] = true;
for(int i=0;i<graph[current].size();i++)
{
if(!visited[graph[current][i]])
{
cost[graph[current][i]] = min( cost[graph[current][i]] ,cost[current] + weight[current][i]);
pq.push(graph[current][i]);
}
}
}
return cost[to];
} |
Après un grand nombre d'appel j'ai une erreur bad allocation(). Après avoir consulté mon ami Google je me suis penché sur l'utilisation de la RAM par le programme et il me semble que cette erreur est due à l'utilisation complète de la RAM (plus d'allocation possible). Je ne maitrise pas les questions de mémoire dans le stack ou dans le heap, mais je pense que c'est lié à ca. En fait initialement je ne pensais même pas avoir besoin de vider la mémoire (pas de new(), donc pas de delete()), mais il s'avère que si je ne le fait pas ca pompe toute la ram. J'ai donc ajouté un petit bout de code qui permet de résoudre le problème:
Code:
1
2
3
4
5
| void clean_queue(void) {
while(!pq.empty()) {
pq.pop();
}
} |
c'est à dire que je dépile toute la queue à la fin de chaque utilisation de cette fonction. Ca fonctionne beaucoup mieux, plus de problème d'allocation, par contre le fait de dépiler à chaque fois que j'ai fini d'utiliser un graphe particulier c'est effroyablement lent, même sur des petits graphes. En fait c'est même plus sournois que ca: sur les premiers graphes (cad première itérations) ca fonctionne bien, puis ca ralentit progressivement jusqu'à devenir très (TRES) lent. Donc je pense que j'ai seulement déplacé le problème et que vider l'espace mémoire est très couteux.
D'où ma question: quelle solution adopter dans ce cadre pour maintenir une gestion mémoire efficace?
Merci!
