Discussion :

[ImmoTPA]

Bonjour à tous,

J'essaie d'implémenter l'algorithme de Bellman-Ford qui permet de calculer les plus courts chemins à partir de sommets sources dans un graphe orienté pondéré. Je crois que mon implémentation donne le bon résultat (ce que je ne peux vérifier) mais mon programme tourne beaucoup trop lentement. J'aimerais donc l'accélerer de manière significative. Voici le code :

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
#include <iostream>
#include <array>
#include <map>
#include <fstream>
#include <climits>
#include <set>
 
struct Edge
{
	unsigned int tail;
	unsigned int head;
	int length;
} ;
 
struct Key
{
	long unsigned int q;
	long unsigned int t;
};
 
struct KeyCompare {
	bool operator()(const Key& a, const Key& b){
		return (a.q < b.q) or (a.q == b.q and a.t < b.t);
	}
};
 
typedef std::map<Key, int, KeyCompare> Graph;
 
Graph get_graph();
int** initialize(unsigned int source);
void compute(int** & tab);
Edge compute_min_edge(unsigned int source, Graph g);
 
Edge compute_min_edge(unsigned int head_, Graph g){
	Edge e({INT_MAX, head_, INT_MAX});
	for(unsigned int x(0); x < 1000; ++x){
		if(g.find({x, head_}) != g.end()){
			if(g.find({x, head_})->second < e.length){
				e.length = g.find({x, head_})->second;
				e.tail = x;
			}
		}
	}
 
	return e;
}
 
 
Graph get_graph(){
	Graph graph;
	std::string ligne("");
	std::ifstream fichier("g1.txt", std::ios::in);
 
	if(fichier){
		getline(fichier, ligne);
		while(getline(fichier, ligne)){
			Key k = {stoul(ligne.substr(0, ligne.find(' ', 0)))-1, stoul(ligne.substr(ligne.find(' ', 0), ligne.find(' ', ligne.find(' ', 0) + 1)))-1};
			graph[k] = stoi(ligne.substr(ligne.find(' ', ligne.find(' ', 0) + 1)));
		}
	}
 
	return graph;
}
 
int** initialize(unsigned int source){
	unsigned int dimX = 1000, dimY = 47978;
	int** tableau;
 
	tableau = new int*[dimX];
	for(size_t x(0); x < dimX; ++x){
		tableau[x] = new int[dimY];
		for(size_t y(0); y < dimY; ++y){
			tableau[x][y] = INT_MAX;
			if(y == 0 and x == source)
				tableau[x][y] = 0;
		}
	}
 
	return tableau;
}
 
void compute(int** & tab, Graph g){
	for(size_t i(1); i < 47978; ++i){
		for(size_t j(0); j < 1000; ++j){
			Edge e(compute_min_edge(j, g));
			tab[i][j] = std::min(tab[i-1][j], tab[i-1][e.tail] + e.length);
			std::cout << " i " << i << std::endl;
		}
	}
}
 
 
int main(int argc, char* argv[]){
 
	Graph graph(get_graph());
 
	int** tab(initialize(0));
 
	compute(tab, graph);
 
	return 0;
}

Comme vous pouvez le voir 3 fonctions sont appelées dans le main, les deux premières cumulées tournent en moins de 1 sec donc le problème vient de la fonction "compute". Or dans cette fonction il y a deux choses principales, une double boucle que je ne peux pas éviter à ma connaissance, des "look-up" répétés dans ma map qui contient mes arêtes. J'imagine que c'est donc ici que je perds du temps. Si quelqu'un a la moindre idée sur la manière d'accélerer mon programme que ce soit avec mes structures ou avec d'autres je vous serais reconnaissant d'en faire part , merci à tous.

[ternel]

Premier réflexe, 47 millions de int? tu es sur de ton coup, là?
Et en plus, il n'y a aucun delete...

Après, ton code est un peu amusant, il est à mi chemin entre le C et le C++.
Je commence à le restructurer un peu de mon coté, pour me creuser un peu la tête.

Pourrais tu nous donner un petit fichier de graphe? une douzaine d’arêtes, par exemple, ça permettrait d'exécuter ton programme.

Autre remarque, le nom du fichier devrait être donné en argument de get_graph().

map.find() est plutot lent, en log(n), donc dans compute_min_edge, il faut le sauvegarder localement, plutot que de le calculer trois fois à chaque passage.

[ImmoTPA]

Bonjour et merci de ta réponse ! Oui tu as raison j'ai oublié de delete (où dois-je les mettre ? ), mon code est à mi-chemin car j'ai appris à coder en C (j'en ai fais un peu) et maintenant j'apprends à coder en C++, mais pour les exercices que je fais ici j'aimerai dans la mesure du possible éviter l'orienté objet si c'est ce à quoi tu pensais à moins que ce ne soit la seule solution. Euh oui malheureusement je suis sûr de mon coup, je programme cet algorithme pour un cours en ligne et c'est le graphe fourni par le cours en question. Et tu as aussi raison je devrai mettre le nom du fichier en argument, j'en suis conscient mais dans la mesure où le challenge et le fun réside pour moi dans l'implémentation de l'algorithme je ne fais pas forcément tout parfaitement en dehors désolé :p.

J'essaie de te construire un graphe qui puisse te servir à run le programme.

[ImmoTPA]

Voilà, le fichier est sous la même forme que celui sur lequel je travaille, sur la premiere ligne tu as le nombre de sommets puis le nombre d'arêtes.
Sur toutes les autres lignes tu as sommet1 puis sommet2 puis poids de l'arête sommet1-sommet2. Il est en pièce jointe

[ternel]

Si tu apprends le C++, je t'invite à lire notre faq, elle t'apprendra plein de choses sur le pourquoi coder de telle ou telle manière.

L'avantage du C++, c'est qu'il propose des classes ayant des attributs privés, et des fonctions.
Ca permet d'augmenter la sécurité de ce qu'on fait.

Par exemple, plutot qu'un tableau de 1000 bidules, on utilise un vector<bidule> de taille 1000. Un vector est de taille variable, et possède les memes performances qu'un tableau (c'en est un en interne).

de meme, plutot que tes stoul, on utiliserai istringstream, et son opérateur >>, permettant justement de lire directement un entier.

Je vais recoder en C++ classique ton code, pour que tu vois ce que ca donne.

[ImmoTPA]

Très bien merci du conseil je lirai la faq autant que possible. Je connais le concept d'orienté objet, j'ai fais du java . Je connais aussi les vector mais on m'a appris que lorsque je connais à l'avance
la taille de mon tableau un array est plus facile à utiliser, si tu entendais par là qu'un vector me permettrait de m'adapter plus rapidement à des changements de taille de l'input je suis parfaitement d'accord avec toi et je suis désolé de me répéter mais pour l'instant j'essaie de faire fonctionner mes algorithmes correctement et en des temps raisonnables (ce qui n'est déjà pas une mince affaire) donc je n'ai pas beaucoup de temps à passer sur ce genre d'optimisation. En revanche je ne connais pas du tout les istreamstring dont tu parles, je te remercie beaucoup de tes efforts et attends impatiemment de voir ton code.

[foetus]

Ce que je remarque dans ta méthode compute_min_edge tu appelles 2 à 3 fois g.find({x, head_}) ou