Bonjour tout le monde, je voudrais remercier par avance tous ceux qui m'aideront avec mon problème.

Voilà j'essaie d'implémenter l'algorithme de Papadimitriou pour résoudre le "2SAT" problem.

A l'heure actuelle j'ai décidé comme conseillé de réaliser un travail préliminaire sur les données pour réduire la taille du problème. En effet le fichier est donné sous la forme suivante :
-x1 x2
x3 x4
-x5 -x6
...
...

chaque fois qu'il y a un - cela signifie "non" (logique puisque les variables xi sont booléennes).

Le travail préliminaire est le suivant : en lisant le fichier je stock les variables précédées du - dans un std::set<long int> negations et les autres dans un std::set<long int> variables

Ensuite je parcours le set de variables et je regarde si chaque variable est aussi présente dans le set de négations (si ce n'est pas le cas les contraintes qui impliquent la variable en question peuvent etre supprimées du probleme donc les boucles ultérieures sur ces contraintes seront bcp moins longues).

Ce qui m'interpelle c'est le code suivant :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
void simplify_problem(problem& prob) {
	for(auto e = prob.variable_iterator(); e!= prob.no_more_variable(); ++e){
		if(prob.get_negations().find(*e) == prob.no_more_negation()){
			prob.remove_variable(*e);
		}
	}
}
il est extrêmement long à executer et pourtant je ne fais pas encore tout le travail que je devrais (à savoir supprimer les contraintes et faire la même chose mais cette fois ci en parcourant le set de négations).

Mes sets contiennent environ 65 000 valeurs, j'ai regardé et itérer sur ces sets en affichant les valeurs prend à peine 1 sec, tandis que ma fonction prend plusieurs minutes. Je sais que la fonction "find" a une complexité logarithmic (donc log 65000 soit < 5) et donc je comprends que ce soit plus long, mais à mon sens ça ne devrait pas être à ce point plus long.

Quelqu'un a une idée de ce qui ralentit mon programme ? merci infiniment