Un doute existenciel a propos du parcours de liste dans une boucle 'for'

Question à deux balles :

Je dirais plutôt que c'est une bonne question.

A tous les coups, le compilo n'a aucun moyen
d'extraire la valeur de liste.end() une fois pour toute avant le début
de la boucle, du coup à chaque itération de la boucle le programme se
retape l'appel à liste.end() !

En effet.

La question toute simple que je me pose est donc : est-ce que c'est pas
mieux de faire

iterator end=liste.end()
for ( iterator it=liste.begin() ; it!=end ; ++it )

Absolument.

Dans le même ordre d'idée, c'est bien ++i comme tu l'as dit et pas i++,
parce que ce dernier crée un objet iterator temporaire.


--
Alain

meow wrote:

for ( iterator it=liste.begin() ; it!=liste.end() ; ++it )

Question à deux balles : A tous les coups, le compilo n'a aucun moyen
d'extraire la valeur de liste.end() une fois pour toute avant le début
de la boucle, du coup à chaque itération de la boucle le programme se
retape l'appel à liste.end() !

Si, le compilateur peut faire l'optimisation tout seul s'il arrive
à déterminer que la valeur de retour ne change pas. Concrètement,
il faudra sûrement que la fonction end() soit inline et que le
contenu de la boucle soit assez simple pour que le compilateur
puisse voir que l'objet liste n'est pas modifié.

La question toute simple que je me pose est donc : est-ce que c'est pas
mieux de faire

iterator end=liste.end()
for ( iterator it=liste.begin() ; it!=end ; ++it )

Mieux en terme de nombre de caractères à taper, non. Mieux en
terme de rapidité d'execution, peut-être, ou peut-être pas.
À réserver aux (rares) cas ou il y a un problème de performance.

--
Sylvain Togni

iterator end=liste.end()
for ( iterator it=liste.begin() ; it!=end ; ++it )

Mieux en terme de nombre de caractères à taper, non. Mieux en
terme de rapidité d'execution, peut-être, ou peut-être pas.
À réserver aux (rares) cas ou il y a un problème de performance.

Ah bon ?
Moi je fais toujours comme ça. Et je suis pas payé à la ligne ;)


--
Alain

Alain Gaillard wrote:

iterator end=liste.end()
for ( iterator it=liste.begin() ; it!=end ; ++it )

Mieux en terme de nombre de caractères à taper, non. Mieux en
terme de rapidité d'execution, peut-être, ou peut-être pas.
À réserver aux (rares) cas ou il y a un problème de performance.

Ah bon ?
Moi je fais toujours comme ça. Et je suis pas payé à la ligne ;)

Moi j'ai jamais eu besoin de faire comme ça. Et je doit donc
avoir un peu plus de temps libre que toi ;)

--
Sylvain Togni

Alain Gaillard wrote:

iterator end=liste.end()
for ( iterator it=liste.begin() ; it!=end ; ++it )

Mieux en terme de nombre de caractères à taper, non. Mieux en
terme de rapidité d'execution, peut-être, ou peut-être pas.
À réserver aux (rares) cas ou il y a un problème de performance.

Ah bon ?
Moi je fais toujours comme ça. Et je suis pas payé à la ligne ;)

Moi j'ai jamais eu besoin de faire comme ça. Et je doit donc
avoir un peu plus de temps libre que toi ;)

LOL :)

--
Alain

du coup à chaque itération de la boucle le programme se
retape l'appel à liste.end() !

Et c'est grave ?
C'est une fonction en O(1).

Regardons par exemple son implémentation dans libstdc++
iterator end() { return &this->_M_impl._M_node; }

Cela construit un iterateur à partir d'un pointeur vers un
_List_node_base, ce qui a un coût négligeable.

À moins que ton profiler ne révèle un problème à cet endroit du
programme, il est inutile d'optimiser ton code de cette manière.

Et c'est grave ?

Je crois me souvenir qu'un gotw dit que oui. Enfin c'est une gravité
toute relative :)

Cela construit un iterateur à partir d'un pointeur vers un
_List_node_base, ce qui a un coût négligeable.

Donc un objet temporaire est construit autant qu'il y a d'itérations.
Alors que c'est tellement simple de l'éviter. D'une manière générale
j'essaie de faire la chasse aux objets temporaires.
Maintenant il n'est pas exclu qu'un bon compilo en mode optimisation
sache éviter la construction de l'objet à chaque itération.

À moins que ton profiler ne révèle un problème à cet endroit du
programme, il est inutile d'optimiser ton code de cette manière.

Je ne parlerais pas d'optimisation, mais simplement d'une bonne habitude
de codage. Pourquoi ne pas éviter les objets temporaires dans les cas où
c'est très simple de le faire ?

--
Alain

On 21 Sep 2006 08:47:23 -0700, "meow" <schwarz.ben@gmail.com>:

iterator end=liste.end()
for ( iterator it=liste.begin() ; it!=end ; ++it )

Du coup, tu sors la variable "end" de la boucle.
En plus, une variable qui a exactement le même nom qu'une fonction, je
n'aime pas trop.

Tu peux éventuellement, sur un nouveau projet, décider qu'une telle
boucle sera systématiquement écrite

for (iterator it= liste.begin(), fin= liste.end();
it != fin; ++it)

Quant à savoir si ça améliore la vitesse du programme, ben...
vraisemblablement, ça dépend fortement de l'application, du
compilateur, voire du processeur. Mais je serais vraiment surpris que
tu trouves beaucoup de cas où la différence est mesurable.

L'important est que ton code soit lisible, c'est pourquoi je te
conseille de choisir un style, et de l'utiliser partout.

M'enfin bon, "normalement" on n'utilise pas de boucles, mais des
algorithmes et des foncteurs.

Alain Gaillard wrote:

Question à deux balles :

Je dirais plutôt que c'est une bonne question.

A tous les coups, le compilo n'a aucun moyen d'extraire la
valeur de liste.end() une fois pour toute avant le début de
la boucle, du coup à chaque itération de la boucle le
programme se retape l'appel à liste.end() !

En effet.

La question toute simple que je me pose est donc : est-ce
que c'est pas mieux de faire

iterator end=liste.end()
for ( iterator it=liste.begin() ; it!=end ; ++it )

Absolument.

Dans le même ordre d'idée, c'est bien ++i comme tu l'as dit et
pas i++, parce que ce dernier crée un objet iterator
temporaire.

Tu l'as mesuré ? Parce que quand j'ai fais des mesures avec
l'implémentation g++, je n'ai trouvé aucune différence (à
l'encontre de lire end() avant, qui a un effet mesurable si on
ne fait rien dans la boucle).

Dans l'ensemble, je crois qu'on peut dire que déclarer une
variable uniquement pour lire end() qu'une fois est une
optimisation prémature, au moins que le profiler dit que c'est
nécessaire. Quant à ++i plutôt que i++, pourquoi pas, s'il n'y a
pas d'autres raisons qui entre en ligne de compte (comme, par
exemple, du code existant qui utilise i++).

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Alain Gaillard wrote:

Et c'est grave ?

Je crois me souvenir qu'un gotw dit que oui.

Je crois que le gotw parlait plutôt de ++ i contre i ++.

Je crois également que Herb n'avait pas mesuré avant de
l'écrire. Le plus qu'on peut dire, c'est que ++ i ne serait pas
moin rapide. Mais jusqu'ici, je n'ai pas trouvé de cas où il y
avait une différence.

Enfin c'est une gravité toute relative :)

Cela construit un iterateur à partir d'un pointeur vers un
_List_node_base, ce qui a un coût négligeable.

Donc un objet temporaire est construit autant qu'il y a
d'itérations.

Ou non. Un bon optimisateur peut faire beaucoup.

Alors que c'est tellement simple de l'éviter.

Une déclaration en plus. Une variable en plus. Pour rien.

Non, merci.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34