Exercice: Optimisations

Exercice: Optimisations#

Notre fonction decouper, telle que vue en cours, est simple à implémenter et à une complexité linéaire optimale. On a toutefois vu qu’il est possible de l’implémenter plus efficacement, soit en parcourant directement la moitié des éléments pour trouver le point ou couper, soit en utilisant des pointeurs se déplaçant à des vitesses différentes. Implémentez l’une de ces variantes et comparez les temps d’execution du tri fusion sur de grandes listes.

BEGIN SOLUTION

La version la plus classique et rapide est la suivante: elle laisse la première moitié des éléments dans la liste d’origine et déplace d’un seul coup la deuxième moitié dans la liste résultat. La logique n’est pas très complexe mais les détails sur comment parcourir exactement le bon nombre d’éléments et comment calculer les longueurs des deux listes ne sont pas forcéments évidents.

On peut voir un petit gain de temps sur les listes de grandes tailles.
```
liste *decouper(liste *l) {
    liste *r = nouvelle_liste();
    if (l->nbelem < 2)
        return r;
    int n = l->nbelem / 2;
    elem *e = l->tete;
	// ici e est le 1er élément de la liste l
    for (int i = 1; i < n; i++)
		// Invariant: e est le i-ème élément
        e = e->next;
	// ici e est le n-ième, e->next le (n+1)-ième
    r->tete = e->next;
    e->next = NULL;
    r->nbelem = l->nbelem - n;
    l->nbelem = n;
    return r;
}
```
END SOLUTION

Notre fonction fusionner peut elle aussi être optimisée: l’utilisation de la fonction deplacer_tete permet en effet de ne pas avoir à s’occuper du chaînage mais a pour résultat de produire une liste à l’envers qu’il faut ensuite renverser.

Définissez une nouvelle fonction fusionner qui garde un pointeur sur le dernier élément de la liste résultat afin de pouvoir insérer les éléments directement à leur place dans la liste.

Attention

La logique de cette fonction n’est pas très complexe mais la multiplicité des cas possibles la rend relativement longue par rapport aux autres fonctions que vous avez pu écrire et rend son test plus difficile.

Veillez notamment à bien gérer les différents cas limites.

BEGIN SOLUTION

liste *fusionner(liste *l1, liste *l2) {
    liste *r = nouvelle_liste();
    // p est un pointeur vers le dernier element de la liste resultat, on
    // l'initialise à NULL pour indiquer qu'actuellement elle est vide.
    elem *p = NULL;
    while (l1->nbelem != 0 && l2->nbelem != 0) {
        // On commence par détacher le plus petit element de
        // sa liste.
        elem *e;
        if (l1->tete->val < l2->tete->val) {
            e = l1->tete;
            l1->tete = e->suivant;
            l1->nbelem--;
        } else {
            e = l2->tete;
            l2->tete = e->suivant;
            l2->nbelem;
        }
        e->suivant = NULL;
        // Puis on l'attache à la fin de la liste résultat.
        if (p == NULL)
            r->tete = e;
        else
            p->suivant = e;
        r->nbelem++;
        p = e;
    }
    // Une des deux liste est vide, il reste juste à deplacer la queue de
    // celle qui ne l'est pas vers la liste résultat.
    liste *l;
    if (l1->nbelem != 0) l = l1;
    else                 l = l2;
    if (p == NULL)
        r->tete = l->tete;
    else
        p->suivant = l->tete;
    r->nbelem += l->nbelem;
    l->nbelem = 0;
    // On n'oublie pas de libérer les listes
    liberer_liste(l1);
    liberer_liste(l2);
    return r;
}

END SOLUTION