Lenteur inexpliquée d'une fonction
Bonsoir,
Pour vous aider à situer la chose, en résumant, j'ai implanter l'algorithme de dijkstra sur des graphes en C++ avec la file de priorité tableau décroissant.
Je le fais afin de faire des test pratique sur les tableaux décroissants puis ensuite les tas binomiaux.
Après avoir créé mes différentes classes, je me rends compte (après plusieurs test) que ce qui ralenti mon programme est la récupération du poids de 2 arrêtes, voici le code :
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
| class Voisin
{
private:
int _sommet;
double _poids;
[...]
};
class TabVoisin
{
private:
list<Voisin> _liste;
Point _coordonnee;
[...]
};
class Graphe
{
private:
int _nbsommet;
vector<TabVoisin> _tableau;
public:
[...]
double Poids(int u, int v);
[...]
};
double Graphe::Poids(int u, int v)
//On est sûr que u et v sont relié
{
vector<TabVoisin> TV=this->get_TabVoisin();
TV[u].get_liste();
list<Voisin> L=TV[u].get_liste();//Renvoie _liste
while(!L.empty())
{
if(L.front().get_sommet()==v)
return L.front().get_poids();
L.pop_front();
}
} |
Pour être sûr que c’est cette fonction qui me fait lagger, mon programme se lance en 2 secondes quand je remplace ce code par :
Code:
1
2
3
4
5
| double Graphe::Poids(int u, int v)
//On est sûr que u et v sont relié
{
return(1);
} |
Et lorsque je le laisse, il mets plusieurs minutes à se lancer. Le graphe possède 200 sommets avec environ une 40aine d'arrêtes par sommet.
Une explication :/ ?
