🚀 go-pugleaf

Charlie Gordon a �crit :

>>>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).

Disons que c'est une routine qui ne doit pas �tre utilis�e ailleurs... 
Le probl�me est que, si le cas pathologique est suffisament rare, le 
traiter syst�matiquement a un co�t plus important que l'ignorer.

>>>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.

C'est �crit quelque part, mais mon exemple ne reprenait pas les 
commentaires.

>>>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.

-- 
Richard