On mesure plutôt le nombre d'instructions.
... que tu définis comment ?
On mesure plutôt le nombre d'instructions.
... que tu définis comment ?
On mesure plutôt le nombre d'instructions.
... que tu définis comment ?
Richard Delorme wrote on 12/09/05 :Les lignes d'aération ne sont pas compté par les programmes qui
comptent les lignes de codes *significatives*.
La notion de ligne de code n'existe pas en C (C != Assembleur). On
mesure plutôt le nombre d'instructions.
Richard Delorme wrote on 12/09/05 :
Les lignes d'aération ne sont pas compté par les programmes qui
comptent les lignes de codes *significatives*.
La notion de ligne de code n'existe pas en C (C != Assembleur). On
mesure plutôt le nombre d'instructions.
Richard Delorme wrote on 12/09/05 :Les lignes d'aération ne sont pas compté par les programmes qui
comptent les lignes de codes *significatives*.
La notion de ligne de code n'existe pas en C (C != Assembleur). On
mesure plutôt le nombre d'instructions.
"Richard Delorme" wrote in message
news:4324794b$0$303$
Cela dépend énormément des données : ton algorithme a une complexité
quadratique, ce qui signifie qu'il prend un temps proportionnel au carré de
la
longueur de la liste, le cas le pire étant celui de la liste déjà triée (!).
Possible, mais le pire cas est excessivement rare.
En
revanche la complexité de qsort est n * log(n) ce qui est bien plus
favorable
pour des valeurs de n suffisamment grandes. Quelle est en moyenne la taille
de
tes listes ?
environ 10, au maximum (très rare) 32, au minimum 1. Le fait que qsort()
doit appeler une fonction de comparaison externe le ralentit beaucoup en
pratique.
Note de plus que ton implémentation plante si la liste est vide.
Impossible, on a toujours un coup à jouer (passer son tour est un coup
légal dans mon implémentation).
La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus
efficace.
Enfin il est facile d'accélérer le cas pathologique de la liste déjà
partiellement ou totalement triée.
void movelist_sort(MoveList *movelist) {
Move *i, *pi, *j, *pj;
pi = movelist->move->next;
if (pi == NULL)
return;
for (; (i = pi->next) != NULL; pi = i) {
if (i->val >= pi->val)
continue;
for (pj = movelist->move; (j = pj->next) != i; pj = j) {
if (j->val < i->val) {
pj->next = i;
pi->next = i->next;
i->next = j;
i = pi;
break;
}
}
}
}
A toi de voir si cela change les performances.
En effet. Sur une série de position de tests tirée d'une revue de la
fédération française d'Othello :
Avant :
fforum-20-39.scr : 138939725 nodes in 00:00:29.9, 4634809 N/s
Après, avec l'algorithme modifié de Chqrlie Gordon :
fforum-20-39.scr : 2400849827 nodes in 00:06:20.9, 6301574 N/s
C'est 13 fois plus lent...
Il y a une erreur dans ton exemple, il ne trie pas les coups... En
corrigeant le « if (i->val >= pi->val) » en « if (i->val <= pi->val) »
et en supprimant l'inutile test de vide liste, on obtient les mêmes
performances qu'avant.
"Richard Delorme" <abulmo@nospam.fr> wrote in message
news:4324794b$0$303$7a628cd7@news.club-internet.fr...
Cela dépend énormément des données : ton algorithme a une complexité
quadratique, ce qui signifie qu'il prend un temps proportionnel au carré de
la
longueur de la liste, le cas le pire étant celui de la liste déjà triée (!).
Possible, mais le pire cas est excessivement rare.
En
revanche la complexité de qsort est n * log(n) ce qui est bien plus
favorable
pour des valeurs de n suffisamment grandes. Quelle est en moyenne la taille
de
tes listes ?
environ 10, au maximum (très rare) 32, au minimum 1. Le fait que qsort()
doit appeler une fonction de comparaison externe le ralentit beaucoup en
pratique.
Note de plus que ton implémentation plante si la liste est vide.
Impossible, on a toujours un coup à jouer (passer son tour est un coup
légal dans mon implémentation).
La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus
efficace.
Enfin il est facile d'accélérer le cas pathologique de la liste déjà
partiellement ou totalement triée.
void movelist_sort(MoveList *movelist) {
Move *i, *pi, *j, *pj;
pi = movelist->move->next;
if (pi == NULL)
return;
for (; (i = pi->next) != NULL; pi = i) {
if (i->val >= pi->val)
continue;
for (pj = movelist->move; (j = pj->next) != i; pj = j) {
if (j->val < i->val) {
pj->next = i;
pi->next = i->next;
i->next = j;
i = pi;
break;
}
}
}
}
A toi de voir si cela change les performances.
En effet. Sur une série de position de tests tirée d'une revue de la
fédération française d'Othello :
Avant :
fforum-20-39.scr : 138939725 nodes in 00:00:29.9, 4634809 N/s
Après, avec l'algorithme modifié de Chqrlie Gordon :
fforum-20-39.scr : 2400849827 nodes in 00:06:20.9, 6301574 N/s
C'est 13 fois plus lent...
Il y a une erreur dans ton exemple, il ne trie pas les coups... En
corrigeant le « if (i->val >= pi->val) » en « if (i->val <= pi->val) »
et en supprimant l'inutile test de vide liste, on obtient les mêmes
performances qu'avant.
"Richard Delorme" wrote in message
news:4324794b$0$303$
Cela dépend énormément des données : ton algorithme a une complexité
quadratique, ce qui signifie qu'il prend un temps proportionnel au carré de
la
longueur de la liste, le cas le pire étant celui de la liste déjà triée (!).
Possible, mais le pire cas est excessivement rare.
En
revanche la complexité de qsort est n * log(n) ce qui est bien plus
favorable
pour des valeurs de n suffisamment grandes. Quelle est en moyenne la taille
de
tes listes ?
environ 10, au maximum (très rare) 32, au minimum 1. Le fait que qsort()
doit appeler une fonction de comparaison externe le ralentit beaucoup en
pratique.
Note de plus que ton implémentation plante si la liste est vide.
Impossible, on a toujours un coup à jouer (passer son tour est un coup
légal dans mon implémentation).
La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus
efficace.
Enfin il est facile d'accélérer le cas pathologique de la liste déjà
partiellement ou totalement triée.
void movelist_sort(MoveList *movelist) {
Move *i, *pi, *j, *pj;
pi = movelist->move->next;
if (pi == NULL)
return;
for (; (i = pi->next) != NULL; pi = i) {
if (i->val >= pi->val)
continue;
for (pj = movelist->move; (j = pj->next) != i; pj = j) {
if (j->val < i->val) {
pj->next = i;
pi->next = i->next;
i->next = j;
i = pi;
break;
}
}
}
}
A toi de voir si cela change les performances.
En effet. Sur une série de position de tests tirée d'une revue de la
fédération française d'Othello :
Avant :
fforum-20-39.scr : 138939725 nodes in 00:00:29.9, 4634809 N/s
Après, avec l'algorithme modifié de Chqrlie Gordon :
fforum-20-39.scr : 2400849827 nodes in 00:06:20.9, 6301574 N/s
C'est 13 fois plus lent...
Il y a une erreur dans ton exemple, il ne trie pas les coups... En
corrigeant le « if (i->val >= pi->val) » en « if (i->val <= pi->val) »
et en supprimant l'inutile test de vide liste, on obtient les mêmes
performances qu'avant.
"Charlie Gordon" writes:Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les
listes qui font 1 ou 2 éléments.
En pratique le bubble sort (ou le shaker sort qui est une variante)
est bien adapte aux cas ou les donnees sont quasiment triees: il peut
avoir un comportement en n sous certaines conditions alors qu'un quick
sort -- mal implemente -- peut meme exhiber un comportement
quadratique . Un bon professionnel -- puisque le terme a ete lance --
va donc l'utiliser dans certains cas.Non, c'est effectivement un tri par insertion (complexité n^2),
nettement plus efficace que bubble sort (n^3 ?),
bubble sort est aussi du n^2 (facile a montrer: a chaque passe au
moins un element en plus est a sa place terminale)
mais moins que qsort (n.log(n)),
qsort c'est difficile a dire, il n'y a pas de contrainte.
L'implementation classique est un quick sort qui a une complexite
quadratique egalement dans le pire cas (attention, suivant la maniere
de choisir le pivot, et les caracteristiques des donnees, le pire cas
peut arriver de maniere certaine dans des cas courants) mais n log n
en moyenne. J'ai deja vu decrite des implementations recourant au
heap sort (garanti n log n -- mais avec une constante relativement
mauvaise) si elles remarquent que la recursion a l'air de prendre un
mauvais bout.
"Charlie Gordon" <news@chqrlie.org> writes:
Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les
listes qui font 1 ou 2 éléments.
En pratique le bubble sort (ou le shaker sort qui est une variante)
est bien adapte aux cas ou les donnees sont quasiment triees: il peut
avoir un comportement en n sous certaines conditions alors qu'un quick
sort -- mal implemente -- peut meme exhiber un comportement
quadratique . Un bon professionnel -- puisque le terme a ete lance --
va donc l'utiliser dans certains cas.
Non, c'est effectivement un tri par insertion (complexité n^2),
nettement plus efficace que bubble sort (n^3 ?),
bubble sort est aussi du n^2 (facile a montrer: a chaque passe au
moins un element en plus est a sa place terminale)
mais moins que qsort (n.log(n)),
qsort c'est difficile a dire, il n'y a pas de contrainte.
L'implementation classique est un quick sort qui a une complexite
quadratique egalement dans le pire cas (attention, suivant la maniere
de choisir le pivot, et les caracteristiques des donnees, le pire cas
peut arriver de maniere certaine dans des cas courants) mais n log n
en moyenne. J'ai deja vu decrite des implementations recourant au
heap sort (garanti n log n -- mais avec une constante relativement
mauvaise) si elles remarquent que la recursion a l'air de prendre un
mauvais bout.
"Charlie Gordon" writes:Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les
listes qui font 1 ou 2 éléments.
En pratique le bubble sort (ou le shaker sort qui est une variante)
est bien adapte aux cas ou les donnees sont quasiment triees: il peut
avoir un comportement en n sous certaines conditions alors qu'un quick
sort -- mal implemente -- peut meme exhiber un comportement
quadratique . Un bon professionnel -- puisque le terme a ete lance --
va donc l'utiliser dans certains cas.Non, c'est effectivement un tri par insertion (complexité n^2),
nettement plus efficace que bubble sort (n^3 ?),
bubble sort est aussi du n^2 (facile a montrer: a chaque passe au
moins un element en plus est a sa place terminale)
mais moins que qsort (n.log(n)),
qsort c'est difficile a dire, il n'y a pas de contrainte.
L'implementation classique est un quick sort qui a une complexite
quadratique egalement dans le pire cas (attention, suivant la maniere
de choisir le pivot, et les caracteristiques des donnees, le pire cas
peut arriver de maniere certaine dans des cas courants) mais n log n
en moyenne. J'ai deja vu decrite des implementations recourant au
heap sort (garanti n log n -- mais avec une constante relativement
mauvaise) si elles remarquent que la recursion a l'air de prendre un
mauvais bout.
En <news:,
Emmanuel Delahaye va escriure:La notion de ligne de code n'existe pas en C (C != Assembleur).
C'est bien connu que les projets sont mesurés en LOA...On mesure plutôt le nombre d'instructions.
... que tu définis comment ?
Pour faire simple, est-ce que cela donne le même nombre de celui de
fonctions (puisque en C, chaque instruction est imbriquée dans une
instruction comme par exemple un bloc, et tout ceci remonte au niveau de la
fonction qui n'admet comme « instruction » que le type « bloc ».
En <news:mn.64837d5995d945e2.15512@YOURBRAnoos.fr>,
Emmanuel Delahaye va escriure:
La notion de ligne de code n'existe pas en C (C != Assembleur).
C'est bien connu que les projets sont mesurés en LOA...
On mesure plutôt le nombre d'instructions.
... que tu définis comment ?
Pour faire simple, est-ce que cela donne le même nombre de celui de
fonctions (puisque en C, chaque instruction est imbriquée dans une
instruction comme par exemple un bloc, et tout ceci remonte au niveau de la
fonction qui n'admet comme « instruction » que le type « bloc ».
En <news:,
Emmanuel Delahaye va escriure:La notion de ligne de code n'existe pas en C (C != Assembleur).
C'est bien connu que les projets sont mesurés en LOA...On mesure plutôt le nombre d'instructions.
... que tu définis comment ?
Pour faire simple, est-ce que cela donne le même nombre de celui de
fonctions (puisque en C, chaque instruction est imbriquée dans une
instruction comme par exemple un bloc, et tout ceci remonte au niveau de la
fonction qui n'admet comme « instruction » que le type « bloc ».
Antoine Leca wrote:un vrai chef (de cuisine).
Je vous conseille 'l'algorithmique du goût' de Brillat-Savarin.
Les professionnels ne donnent que des avis valables en général, par
manque d'informations sur le contexte.
Ëtre pro, ce serait reconnaître ses limites ?
Antoine Leca wrote:
un vrai chef (de cuisine).
Je vous conseille 'l'algorithmique du goût' de Brillat-Savarin.
Les professionnels ne donnent que des avis valables en général, par
manque d'informations sur le contexte.
Ëtre pro, ce serait reconnaître ses limites ?
Antoine Leca wrote:un vrai chef (de cuisine).
Je vous conseille 'l'algorithmique du goût' de Brillat-Savarin.
Les professionnels ne donnent que des avis valables en général, par
manque d'informations sur le contexte.
Ëtre pro, ce serait reconnaître ses limites ?
Cela dépend énormément des données : ton algorithme a une complexité
quadratique, ce qui signifie qu'il prend un temps proportionnel au carré de
la longueur de la liste, le cas le pire étant celui de la liste déjà triée (!).
Possible, mais le pire cas est excessivement rare.
Dans le cas particulier du contexte d'othello, mais quand tu écris une routine
de tri, qui sera peut-etre réutilisée ailleurs, voir mal utilisée (appelée
plusieurs fois) c'est une mauvaise idée d'avoir un comportement inefficace quand
il n'y a rien à faire (liste déjà triée).
Note de plus que ton implémentation plante si la liste est vide.
Impossible, on a toujours un coup à jouer (passer son tour est un coup
légal dans mon implémentation).
Oui, meme remarque que ci-dessus, c'est une contrainte muette qui justifierait
un commentaire d'explications, et éviterait un problème au programmeur suivant
qui voudrait réutiliser ton code sans bien tout comprendre.
La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus
efficace.
On peut peut-être gagner quelques cycles en utilisant une variable locale pour
i->val (je vais supposer que son type est int):
Mais encore faudrait-il que la routine de tri représente une part significative
du temps de calcul, as-tu fait un peu de profiling ?
Cela dépend énormément des données : ton algorithme a une complexité
quadratique, ce qui signifie qu'il prend un temps proportionnel au carré de
la longueur de la liste, le cas le pire étant celui de la liste déjà triée (!).
Possible, mais le pire cas est excessivement rare.
Dans le cas particulier du contexte d'othello, mais quand tu écris une routine
de tri, qui sera peut-etre réutilisée ailleurs, voir mal utilisée (appelée
plusieurs fois) c'est une mauvaise idée d'avoir un comportement inefficace quand
il n'y a rien à faire (liste déjà triée).
Note de plus que ton implémentation plante si la liste est vide.
Impossible, on a toujours un coup à jouer (passer son tour est un coup
légal dans mon implémentation).
Oui, meme remarque que ci-dessus, c'est une contrainte muette qui justifierait
un commentaire d'explications, et éviterait un problème au programmeur suivant
qui voudrait réutiliser ton code sans bien tout comprendre.
La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus
efficace.
On peut peut-être gagner quelques cycles en utilisant une variable locale pour
i->val (je vais supposer que son type est int):
Mais encore faudrait-il que la routine de tri représente une part significative
du temps de calcul, as-tu fait un peu de profiling ?
Cela dépend énormément des données : ton algorithme a une complexité
quadratique, ce qui signifie qu'il prend un temps proportionnel au carré de
la longueur de la liste, le cas le pire étant celui de la liste déjà triée (!).
Possible, mais le pire cas est excessivement rare.
Dans le cas particulier du contexte d'othello, mais quand tu écris une routine
de tri, qui sera peut-etre réutilisée ailleurs, voir mal utilisée (appelée
plusieurs fois) c'est une mauvaise idée d'avoir un comportement inefficace quand
il n'y a rien à faire (liste déjà triée).
Note de plus que ton implémentation plante si la liste est vide.
Impossible, on a toujours un coup à jouer (passer son tour est un coup
légal dans mon implémentation).
Oui, meme remarque que ci-dessus, c'est une contrainte muette qui justifierait
un commentaire d'explications, et éviterait un problème au programmeur suivant
qui voudrait réutiliser ton code sans bien tout comprendre.
La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus
efficace.
On peut peut-être gagner quelques cycles en utilisant une variable locale pour
i->val (je vais supposer que son type est int):
Mais encore faudrait-il que la routine de tri représente une part significative
du temps de calcul, as-tu fait un peu de profiling ?
La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus
efficace.
Je n'ai pas tiqué là dessus la première fois, mais j'ai du mal à
comprendre comment un do/while peut-être moins efficace qu'un while ou
un for, alors qu'il fait une comparaison en moins...
On peut peut-être gagner quelques cycles en utilisant une variable locale
pour
i->val (je vais supposer que son type est int):
A priori non. Le couple compilateur/CPU doit-être suffisament efficace.
Mais encore faudrait-il que la routine de tri représente une part
significative
du temps de calcul, as-tu fait un peu de profiling ?
Actuellement, la part de cette fonction est d'environ 1.5% d'après
gprof, mais :
1) gprof marche mal. Entre deux implémentations, l'une rendant le
programme globalement 1% plus rapide que l'autre, gprof trouve la même
part d'utilisation de 1,5%.
2) j'en suis aux micro-optimisations depuis un moment. Pourcent par
pourcent, j'ai gagné un facteur 5 en vitesse depuis 5 ans.
3) le taux d'utilisation de cette fonction pourrait être supérieur si
elle était plus efficace.
La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus
efficace.
Je n'ai pas tiqué là dessus la première fois, mais j'ai du mal à
comprendre comment un do/while peut-être moins efficace qu'un while ou
un for, alors qu'il fait une comparaison en moins...
On peut peut-être gagner quelques cycles en utilisant une variable locale
pour
i->val (je vais supposer que son type est int):
A priori non. Le couple compilateur/CPU doit-être suffisament efficace.
Mais encore faudrait-il que la routine de tri représente une part
significative
du temps de calcul, as-tu fait un peu de profiling ?
Actuellement, la part de cette fonction est d'environ 1.5% d'après
gprof, mais :
1) gprof marche mal. Entre deux implémentations, l'une rendant le
programme globalement 1% plus rapide que l'autre, gprof trouve la même
part d'utilisation de 1,5%.
2) j'en suis aux micro-optimisations depuis un moment. Pourcent par
pourcent, j'ai gagné un facteur 5 en vitesse depuis 5 ans.
3) le taux d'utilisation de cette fonction pourrait être supérieur si
elle était plus efficace.
La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus
efficace.
Je n'ai pas tiqué là dessus la première fois, mais j'ai du mal à
comprendre comment un do/while peut-être moins efficace qu'un while ou
un for, alors qu'il fait une comparaison en moins...
On peut peut-être gagner quelques cycles en utilisant une variable locale
pour
i->val (je vais supposer que son type est int):
A priori non. Le couple compilateur/CPU doit-être suffisament efficace.
Mais encore faudrait-il que la routine de tri représente une part
significative
du temps de calcul, as-tu fait un peu de profiling ?
Actuellement, la part de cette fonction est d'environ 1.5% d'après
gprof, mais :
1) gprof marche mal. Entre deux implémentations, l'une rendant le
programme globalement 1% plus rapide que l'autre, gprof trouve la même
part d'utilisation de 1,5%.
2) j'en suis aux micro-optimisations depuis un moment. Pourcent par
pourcent, j'ai gagné un facteur 5 en vitesse depuis 5 ans.
3) le taux d'utilisation de cette fonction pourrait être supérieur si
elle était plus efficace.
[...] j'ai du mal à
comprendre comment un do/while peut-être moins efficace qu'un while
ou un for, alors qu'il fait une comparaison en moins...
Elle fait une comparaison en moins, mais le corps de la boucle est
executé une fois de plus avec le do/while dans le cas ou l'élément à
insérer est déjà à sa place en fin de liste.
Mais encore faudrait-il que la routine de tri représente une part
significative du temps de calcul, as-tu fait un peu de profiling ?
Actuellement, la part de cette fonction est d'environ 1.5% d'après
gprof, mais :
cela semble indiquer que tu concentres tes efforts sur le mauvais
cheval.
1) gprof marche mal. Entre deux implémentations, l'une rendant le
programme globalement 1% plus rapide que l'autre, gprof trouve la
même part d'utilisation de 1,5%.
C'est vrai, mais la difference de perf pourrait aussi s'expliquer par
les effets de bord que la modif de cette routine peut avoir sur le
reste du code : par exemple changements d'alignement dans d'autres
fonctions deont le code pourtant identique a ete décalé à cause des
modifs...
2) j'en suis aux micro-optimisations depuis un moment. Pourcent par
pourcent, j'ai gagné un facteur 5 en vitesse depuis 5 ans.
A conditions constantes je suppose?
parce que c'est le rapport moyen
de performances obtenu en suivant betement l'evolution du hard à
logiciel constant. Donc en changeant de machine (pour un prix modique
d'ailleurs) tu devrais avoir un facteur 25.
3) le taux d'utilisation de cette fonction pourrait être supérieur
si elle était plus efficace.
Ca depend de ce que tu entends par là : - tu ferais plus usage de
cette fonction, dans d'autres parties de l'algorithme, ou plus
souvent au cours de l'analyse des coups.
Alors oui, l'optimisation
paierait, mais vu qu'elle ne represente que 1.5% aujourd'hui, tu
pourrais deja mettre cette demarche en pratique.
[...] j'ai du mal à
comprendre comment un do/while peut-être moins efficace qu'un while
ou un for, alors qu'il fait une comparaison en moins...
Elle fait une comparaison en moins, mais le corps de la boucle est
executé une fois de plus avec le do/while dans le cas ou l'élément à
insérer est déjà à sa place en fin de liste.
Mais encore faudrait-il que la routine de tri représente une part
significative du temps de calcul, as-tu fait un peu de profiling ?
Actuellement, la part de cette fonction est d'environ 1.5% d'après
gprof, mais :
cela semble indiquer que tu concentres tes efforts sur le mauvais
cheval.
1) gprof marche mal. Entre deux implémentations, l'une rendant le
programme globalement 1% plus rapide que l'autre, gprof trouve la
même part d'utilisation de 1,5%.
C'est vrai, mais la difference de perf pourrait aussi s'expliquer par
les effets de bord que la modif de cette routine peut avoir sur le
reste du code : par exemple changements d'alignement dans d'autres
fonctions deont le code pourtant identique a ete décalé à cause des
modifs...
2) j'en suis aux micro-optimisations depuis un moment. Pourcent par
pourcent, j'ai gagné un facteur 5 en vitesse depuis 5 ans.
A conditions constantes je suppose?
parce que c'est le rapport moyen
de performances obtenu en suivant betement l'evolution du hard à
logiciel constant. Donc en changeant de machine (pour un prix modique
d'ailleurs) tu devrais avoir un facteur 25.
3) le taux d'utilisation de cette fonction pourrait être supérieur
si elle était plus efficace.
Ca depend de ce que tu entends par là : - tu ferais plus usage de
cette fonction, dans d'autres parties de l'algorithme, ou plus
souvent au cours de l'analyse des coups.
Alors oui, l'optimisation
paierait, mais vu qu'elle ne represente que 1.5% aujourd'hui, tu
pourrais deja mettre cette demarche en pratique.
[...] j'ai du mal à
comprendre comment un do/while peut-être moins efficace qu'un while
ou un for, alors qu'il fait une comparaison en moins...
Elle fait une comparaison en moins, mais le corps de la boucle est
executé une fois de plus avec le do/while dans le cas ou l'élément à
insérer est déjà à sa place en fin de liste.
Mais encore faudrait-il que la routine de tri représente une part
significative du temps de calcul, as-tu fait un peu de profiling ?
Actuellement, la part de cette fonction est d'environ 1.5% d'après
gprof, mais :
cela semble indiquer que tu concentres tes efforts sur le mauvais
cheval.
1) gprof marche mal. Entre deux implémentations, l'une rendant le
programme globalement 1% plus rapide que l'autre, gprof trouve la
même part d'utilisation de 1,5%.
C'est vrai, mais la difference de perf pourrait aussi s'expliquer par
les effets de bord que la modif de cette routine peut avoir sur le
reste du code : par exemple changements d'alignement dans d'autres
fonctions deont le code pourtant identique a ete décalé à cause des
modifs...
2) j'en suis aux micro-optimisations depuis un moment. Pourcent par
pourcent, j'ai gagné un facteur 5 en vitesse depuis 5 ans.
A conditions constantes je suppose?
parce que c'est le rapport moyen
de performances obtenu en suivant betement l'evolution du hard à
logiciel constant. Donc en changeant de machine (pour un prix modique
d'ailleurs) tu devrais avoir un facteur 25.
3) le taux d'utilisation de cette fonction pourrait être supérieur
si elle était plus efficace.
Ca depend de ce que tu entends par là : - tu ferais plus usage de
cette fonction, dans d'autres parties de l'algorithme, ou plus
souvent au cours de l'analyse des coups.
Alors oui, l'optimisation
paierait, mais vu qu'elle ne represente que 1.5% aujourd'hui, tu
pourrais deja mettre cette demarche en pratique.