Titre : zAddition
Mois : novembre
Sujet : Matrice, pure algorithmique

Objectif

L'objectif de zAddition est tout simple (ou pas) : Coder une fonction qui concatène deux matrices. Pour rappel : une matrice est un tableau à deux dimensions. Pour cet exercice, ne vous embêtez pas avec le type des données : prenez des int. Une concaténation est une "fusion", c'est à dire que l'on réunit les deux matrices en une seule et ce grace à la fonction que vous allez devoir coder.
En gros, vous devez réussir à coder un algorithme faisant ceci :

La dimension 1 (M) devra être la même pour chaque matrice. La dimension 2 de la matrice finale sera la somme des dimensions 2 des deux matrices d'entrée. Pour vérifier que l'algorithme fonctionne, on affichera le résultat :

Matrice 1 :
9 6 1 0
2 8 3 4
8 7 5 5

Matrice 2 :
6 1 9 7 1 5
3 7 5 3 8 0
4 8 9 2 3 6

Fusion en cours...

Matrice 3 :
9 6 1 0 6 1 9 7 1 5
2 8 3 4 3 7 5 3 8 0
8 7 5 5 4 8 9 2 3 6

Vous vous organisez comme vous voulez. Pour la structure de votre programme, il devra contenir un main (avec l'affichage des différentes matrices puis de la matrice résultant de la concaténation) et une ou plusieurs fonction(s) pour la concaténation. Pour les matrices, ce que je vous conseille, c'est de créer les trois dans le main, avec les dimensions toutes calculées puis de les envoyer à la fonction. La correction de cette exercice sera donnée dans deux semaines environ.
Je dis : Bonne chance !

crys

Fini :°

Citation : crys'

L'objectif de zAdditon est tout simple

zadditon ou zaddition ?

Citation : crys'

Coder une fonction qui "additionne" deux matrices.

Le terme additionner est très mal choisi vu qu'il existe une opération universellement connue et qui s'appelle ... l'addition de matrices et qui n'a rien à voir avec ce que tu proposes. Le terme de concaténation ou de juxtaposition de matrices est plus approprié.

Par ailleurs, ta spécification est assez vague. Plus éviter les ambiguités, il me semblerait souhaitable que tu proposes un prototype de la fonction à créer.

Les matrices doivent etre définies "en dur" dans le programme ou alors ces matrices doivent être des paramètres "extérieurs" ? (du genre on les entre à la main ou on va les lire dans un fichier texte) ?

Ceci me semble libre, la première solution étant toujours préférable lorsque l'on code une fonction donnée, pour éviter les interférences (problèmes en amont).

Citation : Eusebus

Les matrices doivent etre définies "en dur" dans le programme ou alors ces matrices doivent être des paramètres "extérieurs" ? (du genre on les entre à la main ou on va les lire dans un fichier texte) ?

Je comprends que tu te poses la question car quand je débutais j'étais aussi préoccupé par cela. Fondamentalement, cette question n'a pas d'importance. Tu dois écrire une fonction avec une certaine interface càd les paramètres de la fonction et ce qu'elle renvoie, ensuite tu codes ta fonction pour qu'elle effectue la tache qu'elle a à accomplir (concaténation ici) et seulement après tu adaptes tes entrées pour qu'elles puissent utiliser l'interface de la fonction. Mais l'interface elle ne bouge plus et c'est pour cela qu'il faut qu'elle soit assez bien pensée, dès le départ. Grosso modo, plus ton interface est facile à utiliser moins elle sera susceptible d'évoluer et a contrario, plus ton interface sera riche plus elle sera susceptible d'évoluer mais plus complexe sera son implémentation. Une question naturelle qui se pose ici est la suivante : qui alloue la mémoire pour le tableau concaténé ? la fonction elle-même (ce qui oblige alors à garder trace de l'adresse de l'espace alloué afin qu'ultérieurement la mémoire allouéee soit libérée) ou alors une autre fonction (ce qui oblige à passer en paramètre l'adresse de la zone allouée). Rien de tout cela n'est précisé dans l'énoncé, voilà pourquoi je dis que crys' devrait préciser son énoncé.

C'est surtout que j'étais parti sur l'idée de créer un programme entier pour faire cela, en fait j'avais considéré que le programme (et donc l'implémentation des matrices en dur ou non) faisait partie de l'exercice, alors qu'en fait on ne veut coder que la fonction de concaténation.

Néanmoins, comme tu l'as souligné, il reste légitime de se poser la question en ce qui concerne le tableau concaténé.

Au pire, on peut coder de différentes manières tout cela... Ca reste un bon entraînement <HS>et ça me permet de faire autre chose que mon projet actuel où je rame un peu...</HS>

Edit : Bon, j'ai fait le programme en entier, les matrices sont générées aléatoirement à partir d'arguments que l'on passe à la fonction main (nombre de lignes commun, et nombre de colonnes de chacune des deux matrices).

J'ai édité.

je reprends ce que je disais ici. Le code proposé :

Citation : crys'

void tri_insertion(int* tab, size_t taille)
{
    unsigned i, j;
    int element_a_inserer, temp;

    for(i = 1; i < taille; i++)
    {
        element_a_inserer = tab[i];
        for(j = 0; j < i; j++)
        {
            if (element_a_inserer < tab[j])
            {
                temp = element_a_inserer;
                element_a_inserer = tab[j];
                tab[j] = temp;
            }
        }
        tab[i] = element_a_inserer;
    }
}

peut facilement être modifié pour être à la fois plus naturel (songer à comment on trie ses cartes ce qui est le principe du tri par insertion) et surtout moins lent (le code que je propose est plus de deux fois plus "rapide", bon, "rapide" si l'on peut dire puisque le tri par insertion est un tri qui par nature est lent).

Voici donc mon code :

void isort_int(int *t, size_t n)
{
  size_t aInserer, i;
  int temp;

  for (aInserer = 1; aInserer < n; aInserer++)
    {
      for (temp = t[aInserer], i = aInserer; i > 0 && t[i - 1] > temp; i--)
        t[i] = t[i - 1];
      t[i] = temp;              /* insertion */
    }
}

Comme quoi, même faire un tri simple comme le tri par insertion nécessite qu'on s'y penche avec le soin nécessaire et qu'on se documente si besoin est.

Il s'agit du code de bluestorm.

Citation : crys'

Il s'agit du code de bluestorm.

Les grands esprits se rencontrent Sinon, il est où son code ?

De toute façon, je suis pas très étonné, il n'y a à peu près qu'une façon d'écrire un tri par insertion qui soit correct, il suffit de singer la manière de trier des cartes qu'on aurait dans sa main. Par contre il y a certainement plusieurs manières de l'écrire de manière incorrecte ... Personne ne t'interdit de rectifier les différentes erreurs que comporte ton code (je rajoute d'ailleurs le

return 1 ;

qui est un bug potentiel).

Hum, c'est étrange mais... Le topic n'apparait plus dans le forum, c'est un bug chez moi ou bien ?

Edit : après avoir posté, le topic a réapparu...

J'avais aussi remarqué. J'ai contacté un modérateur et il a réglé le problème visiblement.

Citation : shareman

Il s'agit du code de bluestorm.

[2 janvier 2010 : le EDIT ci-dessous annule les remarques que j'ai faites sur le code de Bluestorm]

Après recherche sur le sdz (tu aurais pu donner le lien), il apparait que bluestorm a écrit un tuto sur le tri par insertion. Hélas pour toi, mon code n'est certainement pas le sien, tu aurais du y regarder avec un peu de finesse et effectuer quelques tests.

Le code de bluestorm met 2 fois et demi plus de temps que le mien et je suis désolé de dire qu'il ne sait pas plus que toi coder un tri par insertion. Son code est ici :

/* 01 */ void tri_insertion(int tab[], int taille)
/* 02 */ {
/* 03 */        int i, j;
/* 04 */        for(i = 1; i < taille; ++i)
/* 05 */        {
/* 06 */               int element_a_inserer = tab[i];
/* 07 */               for(j = 0; j < i; ++j)
/* 08 */               {
/* 09 */                      int element_courant = tab[j];
/* 10 */                        if (element_a_inserer < element_courant)
/* 11 */                      {
/* 12 */                             tab[j] = element_a_inserer;
/* 13 */                          element_a_inserer = element_courant;
/* 14 */                      }  
/* 15 */               }
/* 16 */               tab[i] = element_a_inserer;
/* 17 */        }
/* 18 */ }

Il y a deux maladresses qui expliquent la lenteur relative du code produit, je te laisse les trouver.

Ci-dessous, un test basé sur ton propre code de test (code que j'ai du rectifier à deux endroits pour le rendre portable ... et il aurait d'autres points à reprendre) :

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

void afficher(int *t, int n)
{
  int i;

  for (i = 0; i < n; i++)
    printf("%d ", t[i]);
  printf("\n");
}

/* 01 */ void blue_insertion(int tab[], int taille)
/* 02 */ {
/* 03 */        int i, j;
/* 04 */        for(i = 1; i < taille; ++i)
/* 05 */        {
/* 06 */               int element_a_inserer = tab[i];
/* 07 */               for(j = 0; j < i; ++j)
/* 08 */               {
/* 09 */                      int element_courant = tab[j];
/* 10 */                        if (element_a_inserer < element_courant)
/* 11 */                      {
/* 12 */                             tab[j] = element_a_inserer;
/* 13 */                          element_a_inserer = element_courant;
/* 14 */                      }  
/* 15 */               }
/* 16 */               tab[i] = element_a_inserer;
/* 17 */        }
/* 18 */ }



void isort_int(int *t, size_t n)
{
  size_t aInserer, i;
  int temp;

  for (aInserer = 1; aInserer < n; aInserer++)
    {
      for (temp = t[aInserer], i = aInserer; i > 0 && t[i - 1] > temp; i--)
        t[i] = t[i - 1];
      t[i] = temp;              /* insertion */
    }
}

void charger_tableau(int *sauvegarde, int *tab, size_t taille)
{
  unsigned i;

  for (i = 0; i < taille; i++)
    tab[i] = sauvegarde[i];
}

int hasard(int min, int max)    // fonction de Natim pour les nombres
                                // aléatoires
{
  return (int) (min + ((float) rand() / RAND_MAX * (max - min + 1)));
}

int main(void)
{
  srand(time(NULL));

  int *tab = NULL;
  int *sauvegarde = NULL;
  int taille;
  unsigned i;
  clock_t t1, t2;               // Pour le chrono

  printf(" [zTri] Comparatif de tris \n\n"
         " Choisissez une taille pour le tableau a trier : ");
  scanf("%d", &taille);
  getchar();                    // avaler le '\n' 

  tab = malloc(sizeof(int) * taille);
  sauvegarde = malloc(sizeof(int) * taille);
  /* On crée un tableau de sauvegarde pour qu'un tri suivant un autre n'ai
     pas affaire à un tableau trié mais le même qu'au début du programme */

  if (tab == NULL || sauvegarde == NULL)
    return 0;                   // au cas où les malloc échouent

  for (i = 0; i < taille; i++)
    sauvegarde[i] = tab[i] = hasard(0, taille + 5000);
 /* afficher(tab, taille);*/
  printf("\n");

  printf("\n blue_insertion en cours... ");
  t1 = clock();
  blue_insertion(tab, taille);

  /* afficher(tab, taille); */
  printf("\n");

  t2 = clock();
  printf("blue_insertion : %.3lf secondes \n",
         (double) (t2 - t1) / CLOCKS_PER_SEC);
  charger_tableau(sauvegarde, tab, taille);
  // /////////////////////////////////////////////////////////////
  printf("\n isort_int en cours... ");
  t1 = clock();
  isort_int(tab, taille);
  t2 = clock();
  /* afficher(tab, taille); */
  printf("\n");
  printf("isort_int : %.3lf secondes \n\n",
         (double) (t2 - t1) / CLOCKS_PER_SEC);
  // /////////////////////////////////////////////////////////////

  free(tab);
  free(sauvegarde);

  printf(" Appuyez sur entrer pour quitter...");
  getchar();
  return 0;
}

candide@candide-desktop:~$ gcc -Wall -Wextra -o z sdz_.c
sdz_.c: Dans la fonction «main» :
sdz_.c:85: attention : comparaison entre élément signé et élément non signé
candide@candide-desktop:~$ ./z
 [zTri] Comparatif de tris 

 Choisissez une taille pour le tableau a trier : 30000


 blue_insertion en cours... 
blue_insertion : 5.980 secondes 

 isort_int en cours... 
isort_int : 2.550 secondes 

 Appuyez sur entrer pour quitter...
candide@candide-desktop:~$ ###########################################
candide@candide-desktop:~$ gcc -O2 -Wall -Wextra -o z sdz_.c
sdz_.c: Dans la fonction «main» :
sdz_.c:85: attention : comparaison entre élément signé et élément non signé
candide@candide-desktop:~$ ./z
 [zTri] Comparatif de tris 

 Choisissez une taille pour le tableau a trier : 30000


 blue_insertion en cours... 
blue_insertion : 2.380 secondes 

 isort_int en cours... 
isort_int : 0.990 secondes 

 Appuyez sur entrer pour quitter...
candide@candide-desktop:~$

Ne prends pas mal mes remarques, je pense que tu es un bon codeur et tes offres d'exercices sont une excellente initiative qui permettent de montrer du code C en action. Ce que je veux seulement te dire, c'est que quand on corrige des exercices, il faut mettre le temps qu'il faut pour obtenir un résultat valable et toujours remettre en cause son propre travail. Même si ce n'était pas dur, figure-toi que j'ai quand même mis un certain temps (quelques heures avec les fignolages et les tests divers) avant de produire un code concis et pas trop inefficace (en valeur relative en tous cas). Et j'accepte volontiers les remarques correctives. Désolé mais j'ai un degré d'exigence assez élevé, je fais peu mais j'essaye de faire bien.

EDIT : bluestorm a modifié le code dans son tuto, cf. la discussion ICI.

Je n'ai pas cherché à "bien" implémenter le tri par insertion, bluestorm semblait savoir ce qu'il faisait dans son tuto, j'ai pas cherché à comprendre son code. Merci tout de même pour ton implémentation intéressante, communique-la à bluestorm plutôt.

Et j'ai aussi remarqué que tu me faisais des reproches (sans cesse). Modère tes messages et fais attention à ce que tu dis.

Citation : candide

Il y a deux maladresses qui expliquent la lenteur relative du code produit, je te laisse les trouver.

Je ne sais si j'ai saisi ce que tu veux dire, mais le code "amélioré" ne va pas plus vite (question d'optimisation surement). Et puis de toute façon, le code de bluestorm est certainement a vocation didactique (et non optimisation).

void blue_insertion(int tab[], int taille)
{
    int i, j;
    for (i = 1; i < taille; ++i)
    {
        for (j = 0; j < i; ++j)
        {
            if (tab[i] < tab[j])
            {
                int element_courant = tab[j];
                tab[j] = tab[i];
                tab[i] = element_courant;
            }
        }
    }
}

Il doit y avoir plus qu'un bête probleme de code (je ne me suis pas attardé sur l'algo)...

Citation : yoch

Je ne sais si j'ai saisi ce que tu veux dire, mais le code "amélioré" ne va pas plus vite (question d'optimisation surement).

Quel code amélioré ? celui que tu as écrit ci-dessous ? Il n'y a aucune amélioration, il suffit d'ailleurs de tester pour le voir.

Citation : yoch

(question d'optimisation surement).

Non, pas au sens habituel du terme. Mon code est du code "normal" et simple, il n'est pas optimisé. Du code optimisé, en général, nécessite davantage de code que du code normal parce qu'il faut affiner ce dernier.

Citation : yoch

Et puis de toute façon, le code de bluestorm est certainement a vocation didactique (et non optimisation).

Et alors, est-ce une raison pour donner du code inutilement long et lent à s'exécuter ?

Citation : yoch

Il doit y avoir plus qu'un bête probleme de code...

En effet, c'est un problème d'algorithmique. Remède : prendre un jeu de carte et observer comment on le trie. Ensuite, implémenter cette action de façon la plus fidèle possible.

Mon code est "normal", pas spécialement subtil. Mais il serait possible de l'optimiser (même s'il est assez vain d'optimiser un tri quadratique). Par exemple, ce qui prend du temps est la boucle qui permet de savoir où on va insérer. Pour accélerer la recherche, comme on parcours un tableau déjà trié, au lieu de faire une recherche linéaire, on fait une recherche dichotomique, à mon avis, on obtient un gain vraiment substantiel, je dirais de l'ordre de 20%. Ça c'est une optimisation de haut niveau (car hors langage de programmation). Question optimisation de niveau intermédiaire, probablement (mais à vérifier) changer le décalage séquentiel par une copie globale via la fonction standard memmove voire en utilisant les opérateurs bit à bit puisque on décale une suite d'octets vers la droite (le problème est qu'on perd le bit de parité en utilisant l'opérateur >>).
Il y a aussi des détails qu'on pourrait soigner par exemple si l'élément à insérer doit rester au même endroit ce qui peut arriver sporadiquement, mon code effectue un échange (inutile) de l'élément avec lui-même ce qui peut s'éviter avec un test conditionnel (mais ce test peut lui meme avoir un cout qu'il faut évaluer).

Ce qu'on peut faire aussi pour optimiser (pas tenté) c'est de faire les recherches et insertions deux par deux en utilisant deux variables temporaires ; cela va engendrer un code plus complexe mais, d'une façon générale, c'est le prix de l'optimisation. Je suis convaincu que cette optimisation va apporter un gain vraiment substantiel, je dirais de l'ordre de 30% mais au pris d'une complexité beaucoup plus grande du code.


[Et puis, il reste les optimisations de bas niveau, qu'on repère par profiling et ensuite, éventuellement on récrit certaines routines en assembleur (on perd la portabilité).]

En fait si on veut optimiser un insertion sort, à partir d'un certain niveau de finesse, il faut regarder la littérature spécialisée (il me semble que le shell sort est justement une optimisation du tri par insertion), pour cela Sedgewick est une référence largement admise.


Tout cela pour dire qu'il est absurde d'affirmer que mon code est optimisé vu qu'il est extrêmement simple.

Oui, je suis d'accord avec toi dans l'ensemble (meme si tu n'as pas tout a fait compris ma premiere phrase).

Par curiosité, j'ai réécrit mon code en non-générique pour pouvoir comparer, le tien est plus performant.

void tri_insertion_yoch (int* tab, size_t size)
{
    size_t i, j, n;
    for (i=1; i <size; i++)
    {
        for (j=0; j < i && tab[j] < tab[i]; j++);
        if (j<i)
        {
            int tmp = tab[i];
            for (n = i; n > j; n--)
            {
                tab[n] = tab[n-1];
            }
            tab[j] = tmp;
        }
    }
}

Citation : yoch

(meme si tu n'as pas tout a fait compris ma premiere phrase).

Peux-tu repréciser ce que tu voulais dire ?

Citation : yoch

Par curiosité, j'ai réécrit mon code en non-générique pour pouvoir comparer, le tien est plus performant.

Oui, ça se comprend mais je ne pensais pas que l'écart aurait été aussi important :

candide@candide-desktop:~$ ./z
 [zTri] Comparatif de tris 

 Choisissez une taille pour le tableau a trier : 30000


 yoch_insertion en cours... 
yoch_insertion : 4.080 secondes 

 isort_int en cours... 
isort_int : 2.440 secondes 

 Appuyez sur entrer pour quitter...

Il y a très peu de différence, la seule chose c'est que tu parcours et tu compares une grosse partie de la partie triée (ligne 6) à la recherche de l'indice d'insertion mais je ne pensais pas que ça prenait autant de temps [on pourrait améliorer un peu en décidant de comparer par le haut de la liste triée ou par le bas en fonction de la valeur de la clé à insérer].


Et sinon, effectivement, dans une implémentation générique d'un tri par insertion, je ne vois pas comment on peut échapper à ce calcul préalable.

Citation : candide

Citation : yoch

(meme si tu n'as pas tout a fait compris ma premiere phrase).

Peux-tu repréciser ce que tu voulais dire ?

J'ai essayé de comprendre ce que tu voulais dire par :

Citation : candide

Il y a deux maladresses qui expliquent la lenteur relative du code produit, je te laisse les trouver.

J'ai pensé qu'il s'agissait un probleme de codage (et non d'algo), chose que j'ai tenté de corriger en supprimant les variables superflues, etc. (sans succès comme je l'ai moi même constaté, ce que j'attribue justement a l'optimisation du compilateur).

Bref, j'ai simplement comparé le code de bluestorm avant et après modification. Mais oublions ceci, surtout que je ne suis même pas sur de mon amélioration. A toi plutôt de nous éclairer sur ta véritable intention.

EDIT :
De mon coté, j'ai vu que l'on peut légèrement améliorer mon code (car il est plus rapide d'accéder a une variable qu'au membre d'un tableau) :

void tri_insertion_yoch (int* tab, size_t size)
{
    int *i, *j, *p;
    for (i=tab+1; i <tab+size; i++)
    {
        for (j=tab; j < i && *j < *i; j++);
        if (j<i)
        {
            int tmp = *i;
            for (p = i; p > j; p--)
            {
                *p = *(p-1);
            }
            *j = tmp;
        }
    }
}

Cool des exercices je vais m'y mettre.

bonjour à tous,
je viens de voir les différents code de Yoch,Candide,Chys sur les tris,
merci pour vos échanges d'opinions, pour ma part cela me permet de voir et comprendre autre chose que ce que j'avais fait moi même
Bref, pour ce qui ont envie de progresser et de comprendre ça me va bien !
@+

Citation : candide

Et sinon, effectivement, dans une implémentation générique d'un tri par insertion, je ne vois pas comment on peut échapper à ce calcul préalable.

Ton code peut aussi être écrit de façon générique.

void my_tri_insertion (void *base, size_t nmemb, size_t size, int (*compar)(const void*, const void *))
{
    char *debut = base;
    char *suiv, *ptr;
    char tmp[100];
    for (suiv = debut+size; suiv < debut+(size*nmemb); suiv += size)
    {
        for (ptr = debut; ptr < suiv && compar(ptr, suiv) < 0; ptr += size);
        if (ptr < suiv)
        {
            memcpy(tmp, suiv, size);
            memmove(ptr+size, ptr, suiv-ptr);
            memcpy(ptr, tmp, size);
        }
    }
}

/* algo de candide */
void tri_insertion2 (void *base, size_t nmemb, size_t size, int (*compar)(const void*, const void *))
{
    char *debut = base;
    char *suiv, *ptr;
    char tmp[100];
    for (suiv = debut+size; suiv < debut+(nmemb*size); suiv += size)
    {
        memcpy(tmp, suiv, size);
        for (ptr = suiv; ptr > debut && compar(ptr-size, tmp) > 0; ptr -= size)
        {
            memcpy(ptr, ptr-size, size);
        }
        memcpy(ptr, tmp, size);
    }
}

-----------------
my_tri_insertion OK !

my_tri_insertion en cours sur 30000 entiers tries... 3.656s

my_tri_insertion en cours sur 30000 entiers tries a l'envers... 0.609s

my_tri_insertion en cours sur 30000 entiers aleatoires... 2.203s

-----------------
tri_insertion2 OK !

tri_insertion2 en cours sur 30000 entiers tries... 0.000s

tri_insertion2 en cours sur 30000 entiers tries a l'envers... 10.469s

tri_insertion2 en cours sur 30000 entiers aleatoires... 5.172s

Ce qui est intéressant, c'est que ton tri est alors beaucoup moins performant (sauf sur une liste triée)...

Citation : yoch

J'ai pensé qu'il s'agissait un probleme de codage (et non d'algo), chose que j'ai tenté de corriger en supprimant les variables superflues, etc.
(...)
A toi plutôt de nous éclairer sur ta véritable intention.

Le code de bluestorm comporte deux maladresses d'ordre algorithmique. Je rappelle le code :

/* 01 */ void tri_insertion(int tab[], int taille)
/* 02 */ {
/* 03 */        int i, j;
/* 04 */        for(i = 1; i < taille; ++i)
/* 05 */        {
/* 06 */               int element_a_inserer = tab[i];
/* 07 */               for(j = 0; j < i; ++j)
/* 08 */               {
/* 09 */                      int element_courant = tab[j];
/* 10 */                        if (element_a_inserer < element_courant)
/* 11 */                      {
/* 12 */                             tab[j] = element_a_inserer;
/* 13 */                          element_a_inserer = element_courant;
/* 14 */                      }  
/* 15 */               }
/* 16 */               tab[i] = element_a_inserer;
/* 17 */        }
/* 18 */ }

1ère maladresse : ligne 7 : il n'y aucune raison qu'on parcoure (indice i) toutes les cartes déjà classées (indice j) pour faire l'insertion.

2ème maladresse : lignes 9 à 14 : il n'y pas de raison de systématiquement échanger avec un tampon, il y a juste une seule sauvegarde à faire (la valeur à insérer) ce qui libère une place, place qu'on retrouve en cascade quand on fait le décalage vers la droite (en fait on permute circulairement les valeurs).

Citation : yoch

De mon coté, j'ai vu que l'on peut légèrement améliorer mon code (car il est plus rapide d'accéder a une variable qu'au membre d'un tableau) :

En effet, l'amélioration est très sensible : le temps est presque équivalent à mon code mais ce qu'il y a de TRÈS surprenant c'est que tu as juste fait des changements de noms, l'algorithme est totalement identique, il n'y a ni plus ni moins de recopies.

J'ai effectué les même changements au niveau de mon code et pareil, amélioration spectaculaire, je suis vraiment étonné, j'avais entendu qu'il était préférable de travailler directement avec des pointeurs plutôt qu'avec des tableaux mais je pensais pas que c'était efficace à ce point là (alors qu'en théorie c'est équivalent, le compilateur comprend t[i] comme *(t+i)). En particulier, ce qui semble être efficace c'est d'incrémenter directement un pointeur plutot qu'un indice entier, quand j'aurai le temps, je creuserai la question. L'inconvénient est que le code est moins lisible. Ci-dessous, un comparatif entre nos deux nouveaux codes :

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

void afficher(int *t, int n)
{
  int i;

  for (i = 0; i < n; i++)
    printf("%d ", t[i]);
  printf("\n");
}

void yoch_insertion (int* tab, size_t size)
{
    int *i, *j, *p;
    for (i=tab+1; i <tab+size; i++)
    {
        for (j=tab; j < i && *j < *i; j++);
        if (j<i)
        {
            int tmp = *i;
            for (p = i; p > j; p--)
            {
                *p = *(p-1);
            }
            *j = tmp;
        }
    }
}
#if 1 /* version pointeurs */
void isort_int(int *t, size_t n)
{
  int *aInserer, *fin =t+n;
  int temp;

  for (aInserer = t+1; aInserer < fin; aInserer++)
    {
int *p=aInserer;      
for (temp = *aInserer; p > t && *(p-1) > temp; p--)
        *p = *(p-1);
      *p = temp;             
    }
}
#else /* version tableau */
void isort_int(int *t, size_t n)
{
  size_t aInserer, i;
  int temp;

  for (aInserer = 1; aInserer < n; aInserer++)
    {
      for (temp = t[aInserer], i = aInserer; i > 0 && t[i - 1] > temp; i--)
        t[i] = t[i - 1];
      t[i] = temp;             
    }
}
#endif

void charger_tableau(int *sauvegarde, int *tab, size_t taille)
{
  unsigned i;

  for (i = 0; i < taille; i++)
    tab[i] = sauvegarde[i];
}

int hasard(int min, int max)    // fonction de Natim pour les nombres
                                // aléatoires
{
  return (int) (min + ((float) rand() / RAND_MAX * (max - min + 1)));
}

int main(void)
{
  srand(time(NULL));

  int *tab = NULL;
  int *sauvegarde = NULL;
  int taille;
  unsigned i;
  clock_t t1, t2;               // Pour le chrono

  printf(" [zTri] Comparatif de tris \n\n"
         " Choisissez une taille pour le tableau a trier : ");
  scanf("%d", &taille);
  getchar();                    // avaler le '\n' 

  tab = malloc(sizeof(int) * taille);
  sauvegarde = malloc(sizeof(int) * taille);
  /* On crée un tableau de sauvegarde pour qu'un tri suivant un autre n'ai
     pas affaire à un tableau trié mais le même qu'au début du programme */

  if (tab == NULL || sauvegarde == NULL)
    return 1;                   // au cas où les malloc échouent

  for (i = 0; i < taille; i++)
    sauvegarde[i] = tab[i] = hasard(0, taille + 5000);
/*afficher(tab, taille);*/
  printf("\n");
  // /////////////////////////////////////////////////////////////
  printf("\n yoch_insertion en cours... ");
  t1 = clock();
  yoch_insertion(tab, taille);
  t2 = clock();
 /*afficher(tab, taille); */
  printf("\n");


  printf("yoch_insertion : %.3lf secondes \n",
         (double) (t2 - t1) / CLOCKS_PER_SEC);
  charger_tableau(sauvegarde, tab, taille);
  // /////////////////////////////////////////////////////////////
  printf("\n isort_int en cours... ");
  t1 = clock();
  isort_int(tab, taille);
  t2 = clock();
/*afficher(tab, taille); */
  printf("\n");
  printf("isort_int : %.3lf secondes \n\n",
         (double) (t2 - t1) / CLOCKS_PER_SEC);
  // /////////////////////////////////////////////////////////////

  free(tab);
  free(sauvegarde);

  printf(" Appuyez sur entrer pour quitter...");
  getchar();
  return 0;
}

[zTri] Comparatif de tris 

 Choisissez une taille pour le tableau a trier : 30000


 yoch_insertion en cours... 
yoch_insertion : 2.480 secondes 

 isort_int en cours... 
isort_int : 1.690 secondes 

 Appuyez sur entrer pour quitter...

Au passage, tu pourrais gagner un peu (jusqu'à 3% selon mes essais) en écrivant

int *i, *j, *p, *fin=tab+size;
    for (i=tab+1; i <fin; i++)

au lieu de

int *i, *j, *p;
    for (i=tab+1; i <tab+size; i++)

(peut-être que gcc optimise tout seul si on lui met une option d'optimisation, pas essayé)

Citation : yoch

Ton code peut aussi être écrit de façon générique.

Ah, je vois que tu ne perds pas de temps ! J'en ai écris un générique aussi, basé sur mon tri d'entiers mais je n'ai pas eu le temps de le tester ni éventuellement de l'améliorer et je ne vais pas avoir le temps de regarder tout de suite.

Citation : yoch

-----------------
my_tri_insertion OK !

my_tri_insertion en cours sur 30000 entiers tries... 3.656s

my_tri_insertion en cours sur 30000 entiers tries a l'envers... 0.609s

my_tri_insertion en cours sur 30000 entiers aleatoires... 2.203s

-----------------
tri_insertion2 OK !

tri_insertion2 en cours sur 30000 entiers tries... 0.000s

tri_insertion2 en cours sur 30000 entiers tries a l'envers... 10.469s

tri_insertion2 en cours sur 30000 entiers aleatoires... 5.172s

Ce qui est intéressant, c'est que ton tri est alors beaucoup moins performant (sauf sur une liste triée)...

J'ai plus trop le temps de regarder maintenant mais il y a une différence entre nos deux algorithmes : tu parcoures par le bas les éléments déjà triés et moi par le haut. Ça explique les performances dans le cas des listes triées et comme je l'avais expliqué ci-dessus, il est facile de remédier à ce défaut. Pour le cas des listes aléatoires, il faudrait que j'y regarde plus en détail.

Citation : candide

Citation : yoch

De mon coté, j'ai vu que l'on peut légèrement améliorer mon code (car il est plus rapide d'accéder a une variable qu'au membre d'un tableau) :

En effet, l'amélioration est très sensible : le temps est presque équivalent à mon code mais ce qu'il y a de TRÈS surprenant c'est que tu as juste fait des changements de noms, l'algorithme est totalement identique, il n'y a ni plus ni moins de recopies.

J'ai effectué les même changements au niveau de mon code et pareil, amélioration spectaculaire, je suis vraiment étonné, j'avais entendu qu'il était préférable de travailler directement avec des pointeurs plutôt qu'avec des tableaux mais je pensais pas que c'était efficace à ce point là (alors qu'en théorie c'est équivalent, le compilateur comprend t[i] comme *(t+i)). En particulier, ce qui semble être efficace c'est d'incrémenter directement un pointeur plutot qu'un indice entier, quand j'aurai le temps, je creuserai la question. L'inconvénient est que le code est moins lisible.

Je l'explique comme mentionné plus haut : 'il est plus rapide d'accéder a une variable qu'au membre d'un tableau', car comme tu le dis toi même : 'le compilateur comprend t[i] comme *(t+i)', ce qui fait que pour accéder a t[i], le processeur doit effectuer l'addition (t+i), ce qui n'est pas le cas si le code prend en compte ce détail, auquel cas le processeur ira travailler directement avec ladite variable.

Pour ce qui est de ton code (ou ce que j'explique ne s'applique pas), je ne comprends pas, j'avais aussi tenté de l'écrire en pointeurs, sans aucun résultat, et puis tes 2 codes mettent le même temps chez moi...

PS: chez moi, les différences sont sensibles, mais pas tellement flagrantes. Es-tu sur d'avoir effectué les tests des fonctions dans des conditions similaires (utilisation proc, mémoire, etc.) ?

[zTri] Comparatif de tris

 Choisissez une taille pour le tableau a trier : 30000

 yoch_insertion en cours...
yoch_insertion : 0.844 secondes

 yoch_insertion_ptr en cours...
yoch_insertion_ptr : 0.735 secondes

 isort_int en cours...
isort_int : 0.531 secondes

 isort_int_ptr en cours...
isort_int_ptr : 0.547 secondes

Citation : yoch

Je l'explique comme mentionné plus haut : 'il est plus rapide d'accéder a une variable qu'au membre d'un tableau', car comme tu le dis toi même : 'le compilateur comprend t[i] comme *(t+i)', ce qui fait que pour accéder a t[i], le processeur doit effectuer l'addition (t+i), ce qui n'est pas le cas si le code prend en compte ce détail, auquel cas le processeur ira travailler directement avec ladite variable.

Ce serait aussi mon analyse mais je pense qu'il faut etre assez prudent en la matière.

Citation : yoch

PS: chez moi, les différences sont sensibles, mais pas tellement flagrantes. Es-tu sur d'avoir effectué les tests des fonctions dans des conditions similaires (utilisation proc, mémoire, etc.) ?

Oui, les performances ne sont pas aussi différentes que ça mais quand même plus que chez toi. Elles dépendent aussi des options d'optimisation :

candide@candide-desktop:~$ gcc -Wall -Wextra -o z insertions.c 
insertions.c: Dans la fonction «main» :
insertions.c:80: attention : comparaison entre élément signé et élément non signé
candide@candide-desktop:~$ ./z
 [zTri] Comparatif de tris 

 Choisissez une taille pour le tableau a trier : 100000


 isort_int_pointeurs en cours... 
isort_int_pointeurs : 20.300 secondes 


 isort_int_tableaux en cours... 
isort_int_tableaux : 28.010 secondes 

 Appuyez sur entrer pour quitter...
candide@candide-desktop:~$ gcc -O2 -Wall -Wextra -o z insertions.c 
insertions.c: Dans la fonction «main» :
insertions.c:80: attention : comparaison entre élément signé et élément non signé
candide@candide-desktop:~$ ./z
 [zTri] Comparatif de tris 

 Choisissez une taille pour le tableau a trier : 100000


 isort_int_pointeurs en cours... 
isort_int_pointeurs : 11.560 secondes 


 isort_int_tableaux en cours... 
isort_int_tableaux : 13.990 secondes 

 Appuyez sur entrer pour quitter...

Ça peut dépendre aussi du compilateur, de l'OS, du processeur, de la RAM, du rayonnement cosmique, de la météo ...

Citation : candide

Mon code est "normal", pas spécialement subtil. Mais il serait possible de l'optimiser (même s'il est assez vain d'optimiser un tri quadratique). Par exemple, ce qui prend du temps est la boucle qui permet de savoir où on va insérer. Pour accélerer la recherche, comme on parcours un tableau déjà trié, au lieu de faire une recherche linéaire, on fait une recherche dichotomique, à mon avis, on obtient un gain vraiment substantiel, je dirais de l'ordre de 20%. Ça c'est une optimisation de haut niveau (car hors langage de programmation).

Je suis tout a fait d'accord pour le : 'il est assez vain d'optimiser un tri quadratique'. Par curiosité, je me suis néanmoins amusé a écrire cette optimisation, l'amélioration est réellement spectaculaire (plus de 100%) :

void my_triinsertion_d (int* tab, size_t size)
{
    int *i, *j, *p, *fin = tab+size;
    for (i=tab+1; i < fin; i++)
    {
        /* recherche dichotomique entier supérieur le + proche */
        int *s_debut = tab, *s_fin = i-1;
        while ( (j = s_debut+((s_fin-s_debut)/2)) < s_fin )
        {
            if (*j > *i)
            {
                s_fin = j;
            }
            else if (*j <= *i)
            {
                s_debut = j+1;
            }
        }

        if (*j > *i)
        {
            int tmp = *i;
            for (p = i; p > j; p--)
            {
                *p = *(p-1);
            }
            *j = tmp;
        }
    }
}

void my_tri_insertion_ptr (int* tab, size_t size)
{
    int *i, *j, *p, *fin = tab+size;
    for (i=tab+1; i < fin; i++)
    {
        /* recherche lineaire */
        for (j=tab; j < i && *j < *i; j++);
        if (j<i)
        {
            int tmp = *i;
            for (p = i; p > j; p--)
            {
                *p = *(p-1);
            }
            *j = tmp;
        }
    }
}

[zTri] Comparatif de tris

taille pour le tableau a trier : 50000


 my_tri_insertion_ptr en cours...
my_tri_insertion_ptr : 2.921 secondes

 my_tri_insertion_dichotomique en cours...
my_tri_insertion_d : 1.172 secondes

Citation : candide

(le problème est qu'on perd le bit de parité en utilisant l'opérateur >>).

Pourrais-tu expliquer ?

Citation : candide

Il y a aussi des détails qu'on pourrait soigner par exemple si l'élément à insérer doit rester au même endroit ce qui peut arriver sporadiquement, mon code effectue un échange (inutile) de l'élément avec lui-même ce qui peut s'éviter avec un test conditionnel (mais ce test peut lui meme avoir un cout qu'il faut évaluer).

Oui, ce détail m'a frappé en particulier dans l'algo de tri sélection de crys', qui effectue des permutations inutiles. J'ai effectué un comparatif entre la correction de crys', et l'algo plus classique [*] qui introduit un if en plus. Chez moi, les résultats des deux variantes sont pratiquement les mêmes (même sur un tableau de taille N déjà trié, ou l'algo de crys' effectue N échanges (!), contre zéro pour pour la méthode classique, la différence est très faible !), et la méthode de crys' est même un peu plus rapide sur les petits tableaux...

Conclusion : la méthode employée par crys', quoique contestable en général (surtout dans le cas d'échanges plus couteux, comme par exemple avec un tri générique ou l'échange se fait octet par octet), semble légitime ici. Il faudrait tout de même tester sur d'autres architectures pour vérifier ces observations...

[*] voici l'algo classique du tri sélection (notez la condition surlignée) :

void tri_selection_ptr (int* tab, size_t taille)
{
    int *fin, *i, *plus_grand;
    int temp;
    for (fin = tab+taille; fin > tab; fin--)
    {
        plus_grand = tab;
        for (i = tab+1 ; i <= fin ; i++)
        {
            if (*i > *plus_grand)
                plus_grand = i;
        }
        if (plus_grand != fin)
        {
            temp = *fin;
            *fin = *plus_grand;
            *plus_grand = temp;
        }
    }
}

Citation : yoch

Par curiosité, je me suis néanmoins amusé a écrire cette optimisation,

Bravo, tu n'as vraiment peur de rien.

Citation : yoch

l'amélioration est réellement spectaculaire (plus de 100%) :

Je pensais pas que ça allait autant améliorer le résultat puisque ça n'affecte qu'une partie de l'algorithme, la partie comparaison, la partie recopie n'étant pas concernée par cette amélioration. Au départ j'aurais dit que c'était plutôt la recopie qui était vraiment couteuse. Mais il est connu que le cout relatif de la comparaison par rapport à la recopie dépend des architectures. La valeur de ce cout déterminera le choix du tri élémentaire, essentiellement tri par insertion versus tri par sélection. Les tris élémentaires ne sont pas complètement à négliger car dans les bonnes implémentations d'un quicksort, la récursivité ne va pas jusqu'à des tableaux de taille 1 mais elle s'interromp avant, lorsque les tableaux ont quelques dizaines d'éléments parce qu'il y a un seuil d'effectif où le quicksort est moins efficace qu'un tri élémentaire.

Pour savoir les couts respectifs, faudrait profiler le code (je l'ai jamais fait mais je crois que c'est pas très dur), c'est important en pratique puisque ça permet de savoir dans quelle partie du code il faut privilégier les optimisations, même de haut niveau.

Citation : yoch

Citation : candide

(le problème est qu'on perd le bit de parité en utilisant l'opérateur >>).

Pourrais-tu expliquer ?

Oui, en effet, je comprends tu ne voies pas ce que je veux dire : ce que j'ai dit est incorrect, on ne peut décaler des bits pour décaler des entiers dans un tableau d'entiers.

Citation : yoch

J'ai effectué un comparatif entre la correction de crys', et l'algo plus classique [*] qui introduit un if en plus.

A nouveau, bravo pour ces preuves de rigueur.

Après étude, il y aurait peut-être de quoi améliorer très légèrement le code ci-dessus (tri insertion + recherche dichotomique), en modifiant le comportement en cas d'égalité, ce qui peut parfois (cas de multiples doublons) diminuer sensiblement le nombre de boucles de recherche au prix de quelques permutations en plus, comme ceci :

void my_tri_insertion_d2 (int* tab, size_t size)
{
    int *i, *j, *p, *fin = tab+size;
    for (i=tab+1; i < fin; i++)
    {
        /* recherche dichotomique */
        int *s_debut = tab, *s_fin = i-1;
        while ( (j = s_debut+((s_fin-s_debut)/2)) < s_fin )
        {
            if (*j > *i)
            {
                s_fin = j;
            }
            else if (*j < *i)
            {
                s_debut = j+1;
            }
            else break;
        }

        if (*j >= *i)
        {
            int tmp = *i;
            for (p = i; p > j; p--)
            {
                *p = *(p-1);
            }
            *j = tmp;
            N2++;
        }
    }
}

Cependant, les perfs ne sont pas suffisante a mon sens pour justifier ce nouvel algo, d'autant que le tri perd sa stabilité (l'algo ne garde pas l'ordre relatif des données égales).

Citation : candide

Pour savoir les couts respectifs, faudrait profiler le code (je l'ai jamais fait mais je crois que c'est pas très dur), c'est important en pratique puisque ça permet de savoir dans quelle partie du code il faut privilégier les optimisations, même de haut niveau.

J'ai expérimenté gprof cet après-midi, voici comment faire :

• compiler avec l'option -pg (et surtout pas -s).
• lancer l'exécutable.
• pour un profiling ligne par ligne, faire : gprof -l monexecutable
  
  ou mieux : gprof -l monexecutable > monexecutable.profile.txt

Citation : candide

Les tris élémentaires ne sont pas complètement à négliger car dans les bonnes implémentations d'un quicksort, la récursivité ne va pas jusqu'à des tableaux de taille 1 mais elle s'interromp avant, lorsque les tableaux ont quelques dizaines d'éléments parce qu'il y a un seuil d'effectif où le quicksort est moins efficace qu'un tri élémentaire.

Ainsi regarder le code de remplacement que la SDL propose pour qsort, cf. le fichier SDL_qsort.c :

/* qsort.c
 * (c) 1998 Gareth McCaughan
 *
 * This is a drop-in replacement for the C library's |qsort()| routine.
 *
 * Features:
 *   - Median-of-three pivoting (and more)
 *   - Truncation and final polishing by a single insertion sort
(...)
*/