Discussion :

[sbrisard]

Bonjour à tous,
utilisateur inconditionnel de Java, je me mets à C++ pour des problèmes de rapidité dexécution. Seulement voilà, le même code en C++ tourne PLUS LENTEMENT (environ deux fois moins vite) que son petit frère en Java. Je sais bien que la JVM a fait beaucoup de progrès, mais tout de même, je me dis que mon code C++ ne doit pas être optimal.
Il s'agit d'ajouter dans une boîte de simulation 1d (un intervalle réel) des "particules" (des petits segments) de taille 1.0. La méthode add(double x) ci-dessous tente de faire cela, et renvoie false si la particule que l'on tente d'ajouter recouvre déjà une particule existante. J'ajoute que la boîte est périodique.
Détails de programmation : la variable box est la taille de la boîte, la variable spheres est le nombre de particules déjà contenues dans cette boîte. Les particules sont stockées dans une list<double>, puisque j'ai cru comprendre que l'ajout d'un nouvel élément à n'importe quel endroit de cette liste ne coûte pas cher.
Voilà, voilà, il me reste à joindre le code, en espérant que vous trouverez une optimisation évidente !!! Sinon, j'en resterai à Java...
Merci par avance,
Sébastien

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
 
bool Rsa1d::add(double x) {
	if (center.size() == 0) {
		center.push_back(x);
		++spheres;
		return true;
	}
	list<double>::iterator lower;
	lower = lower_bound(center.begin(), center.end(), x);
	double x1, x2;
	if (lower == center.begin()) {
		x1 = center.back() - box;
		x2 = center.front();
	} else if (lower == center.end()) {
		x1 = center.back();
		x2 = center.front() + box;
	} else {
		x2 = *lower;
		--lower;
		x1 = *lower;
		++lower;
	}
	if ((fabs(x1-x) < 1.0)||(fabs(x2-x) < 1.0)) {
		return false;
	}
	center.insert(lower, x);
	++spheres;
	return true;
}

[Médinoc]

Déjà, la question bête: Est-ce que l'optimisation est activée quand tu compiles ?

PS: std::list<> correspond à java.util.LinkedList. Au niveau algorithme, je pense que c'est optimal...
PPS:

[sbrisard]

Je compile avec l'option -O2, j'espère que c'est suffisant (mais j'aurais tendance à croire que même sans, le programme C++ devrait être plus rapide que le programme Java).
Je pense que la structure de donnée est bien choisie, je me pose des questions quant à l'utilisation des itérateurs dans mon code (je ne maîtrise pas bien les itérateurs à la sauce C++), ainsi que l'algorithme lower_bound : j'ai lu la chose suivante sur www.cplusplus.com à propos de la complexité :
At most, logarithmic number of comparisons and linear number of steps in the length of [first,last). If used with random-access iterators, number of steps is reduced to logarithmic.
Pour moi la complexité devrait être logarithmique dans mon cas, non ?
Merci,
S

[Luc Hermitte]

lower_bound sur une liste (chainée), ce n'est pas vraiment optimal ...
Mieux vaut privilégier les vecteur/deque si tu ne passe pas ton temps à faire des ajouts/retraits en milieu de tes collections. Avec des conteneurs de petites tailles, ils sont aussi acceptables en général.

Tu peux regarder les std::set aussi -- c'est aussi couteux que les listes en parcours itératif, mais en O(ln n) en extraction comme en insersion. Il te faudra fournir le foncteur qui va bien pour déterminer une relation d'ordre entre tes sphères.

fabs ... c'est pour les float non ? (-> conversion). Prend std::abs(), le compilo se chargera ensuite d'utiliser la bonne fonction.

PS: Et édite ton message pour
PPS: je me trompe ou spheres == center.size() ?
PPPS: j'aurais bien conseiller de trier les entrées préalablement, mais vu que l'algo a une mémoire, je sens que cela ne va pas le faire.

[ac_wingless]

Il faut absolument retourner à Java!! C++ çay le mal!
Sérieusement, std::list n'étant pas un conteneur trié, la fonction ne peut qu'être lente. Ce n'est pas un problème d'algorithme, mais de conteneur. En effet, lower_bound ne peut pas vraiment profiter de sa dichotomie avec une liste chainée, car chaque avancement d'indice va faire parcourir tous les noeuds intermédiaires (le pire cas étant une insertion en début de liste, mais même le meilleur cas, à savoir une insertion exactement au milieu, dépointera la moitié des pointeurs de la liste!). En gros, sur une grosse liste, 99.999+% du temps sera passé à dépointer des pointeurs.
Je pense qu'un conteneur trié sera bien plus performant. Il est dommage que le conteneur trié de base de la STL soit std::map, totalement surdimensionné par rapport au besoin. On touche là une des faiblesses du C++, à savoir une librairie standard squelettique comparé à Java ou C#.

[Médinoc]

En plus simple: lower_bound() ne peut pas être complètement logarithmique sur une liste chaînée, car l'accès aléatoire n'y est pas possible. Mais si j'ai bien compris l'extrait de doc, le nombre de comparaisons lui-même est quand même logarithmique.

Pour ton code, il est possible qu'un std::set<> (java.util.TreeSet) soit plus performant, puisque l'insertion sera complètement logarithmique au lieu d'être plus-ou-moins linéaire...

[JolyLoic]

Question : Combien as tu d'éléments dans ta liste ? 3, 10000, 100000000 ?

Ensuite, sur une structure comme list où on ne peut pas faire d'accès direct, mais uniquement case à case, l'algorithme lower_bound est linéaire. Donc non optimal.

Il me semblerait intéressant de regarder avec une structure comme std::set, où la recherche (fonction membre lower_bound, plutôt que l'algorithme) sera en log(n), et l'insertion guidée par le résultat de la recherche sera en temps constant amorti.

Edit : Grillé 4 fois le temps d'écrire ma réponse...

[sbrisard]

Merci pour tous ces commentaires !!!

lower_bound sur une liste (chainée), ce n'est pas vraiment optimal ...
Mieux vaut privilégier les vecteur/deque si tu ne passe pas ton temps à faire des ajouts/retraits en milieu de tes collections. Avec des conteneurs de petites tailles, ils sont aussi acceptables en général.

Justement, j'insère à priori plutôt en milieu de liste...

Tu peux regarder les std::set aussi -- c'est aussi couteux que les listes en parcours itératif, mais en O(ln n) en extraction comme en insersion. Il te faudra fournir le foncteur qui va bien pour déterminer une relation d'ordre entre tes sphères.

Merci beaucoup ! Cela doit correspondre à ce que je cherche !

fabs ... c'est pour les float non ? (-> conversion). Prend std::abs(), le compilo se chargera ensuite d'utiliser la bonne fonction.

Ooops ! Des vieux restes du C... Je vais modifier mon code.

PS: Et édite ton message pour

Done !

PPS: je me trompe ou spheres == center.size() ?

Correct, mais je me disais que j'allais limiter les appels (sans doute très naïf ?).

PPPS: j'aurais bien conseiller de trier les entrées préalablement, mais vu que l'algo a une mémoire, je sens que cela ne va pas le faire.

C'est inutile, car les sphères sont insérées une à une dans la liste au moyen de la seule méthode add(double x) : la liste est donc constamment triée.

[ac_wingless]

Je viens de voir l'endroit d'où la citation est tirée... C'est grossièrement faux. Pas votre faute, il faut bien faire confiance à des sites qui se prétendent didactiques... mais là, vraiment pas de chance. En effet, contrairement à ce qui vous a été indiqué, lower_bound est beaucoup beaucoup moins bien que linéaire sur la taille de la liste. Exemple d'implémentation VS 2008:

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
 
template<class _FwdIt,
	class _Ty,
	class _Diff> inline
	_FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Diff *)
	{	// find first element not before _Val, using operator<
	_DEBUG_ORDER_SINGLE(_First, _Last, true);
	_Diff _Count = 0;
	_Distance(_First, _Last, _Count);
 
	for (; 0 < _Count; )
		{	// divide and conquer, find half that contains answer
		_Diff _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		std::advance(_Mid, _Count2);
		_DEBUG_ORDER_SINGLE(_Mid, _Last, false);
 
		if (_DEBUG_LT(*_Mid, _Val))
			_First = ++_Mid, _Count -= _Count2 + 1;
		else
			_Count = _Count2;
		}
	return (_First);
	}

Je n'ai pas souvenir d'avoir vu la moindre mention de comportement linéaire sur déplacement pour lower_bound dans les listes, à part justement ce site, sur lequel je vais m'empresser de proférer des malédictions vaudou, au cas où ça marcherait.

On voit dans le code ci-dessus que c'est encore pire que ce que j'indique dans mon post ci-dessus: rien qu'avant de lancer la boucle de dichotomie, on dépointe l'ensemble de la liste, juste pour obtenir la taille de recherche! Sur une liste un peu grande, 99.999% du temps passé à dépointer est probablement très optimiste.

[JolyLoic]

L'algo que tu montres m'a tout l'air d'être linéaire. Avec un mauvais coefficient devant, mais linéaire tout de même.

[sbrisard]

Merci à tous pour vos réponses !
Je n'avais donc apparemment pas choisi la bonne structure de données, et je vais basculer sur set à la place de list. J'aurais dû faire plus attention, puisque la structure correspondante que j'utilise en Java est TreeSet...
Je vous tiendrai au courant des gains de temps qui en résultent.
En tous cas, merci pour votre réactivité !
Vous êtes tous des

[Luc Hermitte]

a- Justement, j'insère à priori plutôt en milieu de liste...

b- C'est inutile, car les sphères sont insérées une à une dans la liste au moyen de la seule méthode add(double x) : la liste est donc constamment triée.

a- Sur une petite quantité d'éléments, le vecteur pourra être plus efficace (quelques centaines -> d'où le message de Loïc)

b- Ben, si tu n'avais pas eu ce filtrage bizarre à mémoire, un reserve sur le vecteur, suivi d'un remplissage, et conclu par un std::sort aurait été le plus efficace -> certitude de O(ln n), élimination du besoin en décalage d'éléments pour remplacer cela par des échanges d'éléments.

Je pense qu'un conteneur trié sera bien plus performant. Il est dommage que le conteneur trié de base de la STL soit std::map, totalement surdimensionné par rapport au besoin. On touche là une des faiblesses du C++, à savoir une librairie standard squelettique comparé à Java ou C#.

??? Quoi ?
Et std::set alors ?
On touche aussi à sa richesse : des structures vraiment génériques ...

[ac_wingless]

Ah oui, j'ai été bien trop vite. J'ai fait ma crise cardiaque sur "_Distance(_First, _Last, _Count);" et j'ai pas détaillé la suite. L'algorithme est effectivement linéaire, et même pas plus lent en insertion en début de liste qu'en fin... et en plus, std::set convient tout à fait au problème. 3 gaffes en 2 posts, je me recouche, là

[Bertrand_g]

Bonjour,

En regardant ton code, j'ai quelques questions :
1) La méthode add semble maintenir la liste triée. Or, si tu envisages d'utiliser le set, c'est que cette notion t'importe peu... Vrai ?
2) Peux-tu utiliser le type int à la place de double ?
3) Ton conteneur vise à interdire l'utilisation de doublons. Vrai ?

Si tu peux répondre par l'affirmative à ces trois hypothèses, alors tu peux implémenter assez simplement un conteneur en te basant sur deux vecteurs (l'un contenant les éléments, l'autre la position, "l'adresse" des éléments dans le premier vecteur). Les éléments sont contiguës dans le premier vecteur. L'ajout se fait toujours en fin, la suppression en milieu implique un petit swap. Dans les deux cas, il faut mettre à jour les "adresses".

Tu obtiens alors un container permettant l'ajout, la suppression, le test de présence, l'info sur le nombre d'éléments, en temps constant !

[Médinoc]

Bertrand_g : Je rappelle que std::set<> est trié...

[Bertrand_g]

Oupssss, autant pour moi ! ("Sorted Associative Container")

[sbrisard]

ça y est !!!!
J'ai remplacé mes list<double> par des set<double>, et le programme marche du tonnerre. Il met une grosse claque à son cousin en Java.
Merci à tous, et bonne fin de journée !
Sébastien

[epsilon68]

c'est combien la difference? elle est vraiment grosse la claque?
on peut voir les deux programmes? pour ceux qui doutent ...