🚀 go-pugleaf

"Richard Delorme" <abulmo@nospam.fr> wrote in message
news:43255e40$0$304$7a628cd7@news.club-internet.fr...
> Charlie Gordon a �crit :
> > "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.

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

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

Bonne remarque.  De plus qsort est trop generale, elle est inefficace pour trier
des tableaux de pointeurs � cause des indirections inutiles, quant � trier des
tableaux de structures, c'est inefficace � cause des d�placements couteux qu'un
tableau de pointeurs permet d'�viter.  Conclusion : ne pas utiliser qsort,
organiser ses donn�es pour pouvoir utiliser pqsort, une version qui op�re sur
des tableaux de pointeurs de structures, voire une version custom qui fait les
comparaisons inline pour des structures sp�cifiques.  En C++ on peut utiliser
des templates pour ca, en C il faut �tre particuli�rement hardi pour vouloir
reimplementer qsort pour des types sp�cifiques.

Mais c'est une approche possible, vu que tu connais la taille maximale du
tableau.

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

Effectivement, honte sur moi, la liste est tri�e par ordre d�croissant de val...
je n'avais pas de quoi tester : code non test� = bug probable.

On peut peut-�tre gagner quelques cycles en utilisant une variable locale pour
i->val (je vais supposer que son type est int):

void movelist_sort(MoveList *movelist) {
    Move *i, *pi, *j, *pj;
    int val;

    pi = movelist->move->next;
    if (pi == NULL)
        return;
    for (; (i = pi->next) != NULL; pi = i) {
        if ((val = i->val) <= pi->val)
            continue;
        for (pj = movelist->move; (j = pj->next) != i; pj = j) {
            if (j->val < val) {
                pj->next = i;
                pi->next = i->next;
                i->next = j;
                i = pi;
                break;
            }
        }
    }
}

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 ?

-- 
Chqrlie.