IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

performance : tableau a plusieurs dimensions


Sujet :

C

  1. #1
    Membre confirmé
    Homme Profil pro
    Collégien
    Inscrit en
    Mars 2003
    Messages
    192
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Afghanistan

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Mars 2003
    Messages : 192
    Par défaut performance : tableau a plusieurs dimensions
    Salut,


    J'ai une quantité bi-dimensionnelle : f(i,j) que je veux accéder en lecture et en écriture, rapidement. Le domaine sur lequel f est défini contient beaucoup d'éléments (possiblement plusieurs millions de 'double').

    A chaque élément f(i,j), je vais avoir besoin d'accéder rapidement (en lecture surtout) aux élements "autour", c'est à dire :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    f(i+1,j)
    f(i-1,j)
    f(i,j+1)
    f(i,j-1)

    Je me des questions quant à l'implémentation la plus efficace de ces données du point de vue rapidité.


    J'ai trois solutions (peut-on en imaginer d'autres ?)

    La première consiste a faire un "vrai" tableau 2D dynamique :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    typedef unsigned int uint;
     
    typedef struct array2D
    {
    double **a;
    uint    nx;
    uint    ny;
    } Array2D;

    que je construit comme ceci :


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
     
    Array2D *array2D_new(uint nx, uint ny)
    {
    Array2D *this;
    uint i;
    uint k;
     
    this = calloc(1, sizeof *this);
     
    if (this == NULL)  return NULL;
     
    this->a = calloc(nx, sizeof *this->a);
    if (this->a == NULL)
       {
       free(this);
       return NULL;
       }
     
    for (i=0; i < nx; i ++)
        {
        this->a[i] = calloc(ny, sizeof *this->a[i]);
    	if (this->a[i] == NULL)
           {
           for (k=0; k <= i; k ++)
               free (this->a[k]);
           free(this);
           return NULL;
           }
        }
     
    this->nx = nx;
    this->ny = ny;
     
    return this;
    }

    détruit ainsi :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     
    void
    array2D_delete(Array2D *this)
    {
    uint i;
     
    if (this != NULL)
       {
       for (i=0; i < this->nx; i++)
           {
           if (this->a[i]) free(this->a[i]);
           }
       }
    free(this);
    }


    et pour lequel j'accède aux éléments de cette manière :


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
     
    void array2D_stencil(const Array2D *grid)
    {
    uint i,j;
     
    double tmp;
    uint nx, ny;
     
    nx = grid->nx;
    ny = grid->ny;
     
     
    for (i=1; i < nx-1; i ++)
        {
        for (j = 1; j < ny-1; j++)
            {
            // do some stuff with the four 
            // neighbouring points
            tmp = 0.25*(grid->a[i-1][j  ] +
                        grid->a[i  ][j+1] +
                        grid->a[i+1][j  ] + 
                        grid->a[i  ][j-1]);
            }
        }
    }



    La seconde méthode, consiste à faire un tableau dynamique 1D, et que l'utilisateur calcule lui même l'indice 1D à partir de deux boucles imbriquées sur i et j.

    Ca se déclare comme ceci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    typedef struct _array2D1D
    {
    double *a;
    uint nx;
    uint ny;
    } Array2D1D;

    se construit ainsi :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
     
    Array2D1D *array2D1D_new(uint nx, uint ny)
    {
     
    Array2D1D *this;
     
     
    this = calloc(1, sizeof *this);
     
    if (!this) return NULL;
     
    this->a = calloc(nx*ny, sizeof *this->a);
    if (! this->a) 
       {
       free(this);
       return NULL;
       }
     
    this->nx = nx;
    this->ny = ny;
     
    return this;
    }

    se détruit ainsi

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
     
    void
    array2D1D_delete(Array2D1D *this)
    {
    if (this)
       {
       if (this->a) free (this->a);
       free(this);
       }
    }


    et on accède aux éléments ainsi :


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
     
    void array2D1D_stencil_a(const Array2D1D *grid)
    {
    uint i,j;
    uint ij, ij1, ij2, ij3, ij4;
     
    double tmp;
    double *a;
    uint nx, ny;
     
    nx = grid->nx;
    ny = grid->ny;
     
     
    a = grid->a;
     
     
    //           +ij2
    //           | 
    //           |
    //  ij1      |       ij3
    //  +--------+ij------+
    //           |
    //           |
    //           |
    //           +
    //           ij4
     
     
    for (i=1; i < nx-1; i ++)
        {
        for (j = 1; j < ny-1; j++)
            {
            ij  = (i  ) + (j  )*(nx);
     
            ij1 = (i-1) + (j  )*(nx);
            ij2 = (i  ) + (j+1)*(nx);
            ij3 = (i+1) + (j  )*(nx);
            ij4 = (i  ) + (j-1)*(nx);
     
            // do some stuff with the four 
            // neighbouring points
            tmp = 0.25*(a[ij1] + a[ij2] + a[ij3] + a[ij4]);
            }
        }
    }


    J'ai chronométré les fonctions *_stencil() pour les deux objets, sur des tableaux de 8192*8192 éléments, et ça 10fois de suite, afin de m'assurer que le chronométrage ne dépend pas d'autres processus tournant sur ma machine.


    j'ai été très surpris de constater que la méthode 1 est BIEN plus rapide. En effet, voici les temps, en seconde des deux méthodes :


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
         méthode 1       méthode 2
      1.10430538      8.25240617      
     0.967257762      7.72914395     
     0.963137127      7.71300082     
     0.963082132      7.70107212     
     0.963722737      7.69799643     
     0.969022776      7.80377674     
     0.976541885      7.83630202     
     0.963828863      7.70916793     
     0.964121218      7.71000535     
     0.963386301      7.70990839


    En fait, j'aurai dit que la méthode 1 serait la plus lente. Car la "seconde dimension" du tableau est allouée à un endroit différent dans la mémoire que la première dimension... et chaque ligne de la seconde dimension est allouée à un endroit différent. En allant chercher des valeur aux points (i+1,j), (i-1,j), (i,j+1), (i,j-1) j'aurais donc pensé qu'on allait charger des zones différentes en cache, et perdre en rapidité.

    La méthode 2 en revanche, présente en effet un surcout car elle demande, pour charger un élément à la ligne supérieure (j+1), de charger toutes les données i de la ligne j. Je pensais que ça ne serait pas efficace, mais tout de même plus que la méthode 1, car même si on doit sauter beaucoup de point, les données restent contigues en mémoire.

    Devant le résultat, j'ai pensé que le surcout venait peut-être du calcul d'indice que je fais à chaque fois :


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
            ij1 = (i-1) + (j  )*(nx);
            ij2 = (i  ) + (j+1)*(nx);
            ij3 = (i+1) + (j  )*(nx);
            ij4 = (i  ) + (j-1)*(nx);

    J'ai donc légèrement modifié mon objet, de sorte à ce que les indices des points autour de (i,j) de soient plus calculés à chaque fois, mais calculés une bonne fois pour toute lors de la création de l'objet, pour chaque point (i,j) :


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    typedef struct _array2D1D
    {
    double *a;
    uint nx;
    uint ny;
    uint *stencil[4];
    } Array2D1D;

    le "stencil" est donc un ensemble de 4 indices par point de tableau 'a', il est créé dans le constructeur précédent, un peu modifié pour la cause :


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
     
    Array2D1D *array2D1D_new(uint nx, uint ny)
    {
     
    Array2D1D *this;
    uint i,j,ij;
    uint ij1, ij2, ij3, ij4;
     
     
    this = calloc(1, sizeof *this);
     
    if (!this) return NULL;
     
    this->a = calloc(nx*ny, sizeof *this->a);
    if (! this->a) 
       {
       free(this);
       return NULL;
       }
     
    this->nx = nx;
    this->ny = ny;
     
    // allocation pas verifiee.. a l'arrache
    this->stencil[0] = calloc(nx*ny, sizeof *this->stencil[0]);
    this->stencil[1] = calloc(nx*ny, sizeof *this->stencil[1]);
    this->stencil[2] = calloc(nx*ny, sizeof *this->stencil[2]);
    this->stencil[3] = calloc(nx*ny, sizeof *this->stencil[3]);
     
     
    //           +ij2
    //           | 
    //           |
    //  ij1      |       ij3
    //  +-----+ij------+
    //           |
    //           |
    //           |
    //           +
    //           ij4
     
    for (i=0; i < nx; i++)
        {
        for (j=0; j < ny; j++)
            {
            ij  = (i  ) + (j  )*(nx);
     
            ij1 = (i-1) + (j  )*(nx);
            ij2 = (i  ) + (j+1)*(nx);
            ij3 = (i+1) + (j  )*(nx);
            ij4 = (i  ) + (j-1)*(nx);
     
    		this->stencil[0][ij] = ij1;
    		this->stencil[1][ij] = ij2;
    		this->stencil[2][ij] = ij3;
    		this->stencil[3][ij] = ij4;
     
            }
        }
     
    return this;
    }

    Cette méthode, je pensais, permet de s'affranchir du cout des calculs d'indices, au prix d'un cout mémoire additionnel que je suis prêt à payer.

    l'accès au tableau se fait à présent ainsi :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
     
     
    void array2D1D_stencil_b(const Array2D1D *grid)
    {
    uint i,j;
     
    double tmp;
    double *a;
    uint *ij1;
    uint *ij2;
    uint *ij3;
    uint *ij4;
    uint nx, ny;
     
    nx = grid->nx;
    ny = grid->ny;
     
     
    a = grid->a;
    ij1 = grid->stencil[0];
    ij2 = grid->stencil[1];
    ij3 = grid->stencil[2];
    ij4 = grid->stencil[3];
     
     
    //           +ij2
    //           | 
    //           |
    //  ij1      |       ij3
    //  +--------+ij------+
    //           |
    //           |
    //           |
    //           +
    //           ij4
     
     
    for (i=1; i < nx-1; i ++)
        {
        for (j = 1; j < ny-1; j++)
            {
            // do some stuff with the four 
            // neighbouring points
            tmp = 0.25*(a[ij1[i + j*nx]] + a[ij2[i+j*nx]] + a[ij3[i+j*nx]] + a[ij4[i+j*nx]]);
            }
        }
    }

    Je relance mon code de mesure de temps, et à mes deux colonnes précédentes s'ajoute une troisième, mesurant le temps en secondes passé dans la routine array2D1D_stencil_b()

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
       methode 1       méthode 2        méthode 3
      1.10430538      8.25240617      26.6270934
     0.967257762      7.72914395      26.6097884
     0.963137127      7.71300082      26.6851487
     0.963082132      7.70107212      26.6141512
     0.963722737      7.69799643      26.7747686
     0.969022776      7.80377674      26.8523572
     0.976541885      7.83630202      26.7336635
     0.963828863      7.70916793      26.6687285
     0.964121218      7.71000535      26.6810654
     0.963386301      7.70990839      26.7819276

    Alors ça ! c'est encore beaucoup plus lent que la seconde méthode !!

    en gros, je pensais que les temps seraient :

    méthode3 < méthode2 < méthode 1

    et finalement c'est tout l'inverse !

    Quelqu'un peut-il m'expliquer ça ? Il semble finalement qu'il faille privilégier la méthode 1, et de loin....


    J'ai mis le code dans un zip en pièce jointe. Ca devrait compiler sans probleme avec un simple 'make' sous linux (ça ne tourne pas sous mac, et je ne sais pas pour windows, à cause de la bibliothèque 'lrt').




    Merci
    Fichiers attachés Fichiers attachés

  2. #2
    Expert confirmé
    Avatar de diogene
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    Juin 2005
    Messages
    5 761
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2005
    Messages : 5 761
    Par défaut
    La lenteur de la méthode 2 vient que l'ordre d'accès aux éléments d'un grand tableau est important si le tableau ne tient pas complètement en mémoire cache.
    Ton code de la méthode 2, tel qu'il est, demande sur ma machine environ 8.8s (contre 1.05s pour le code de la méthode 1).
    Si je me contente simplement d'échanger les boucles i et j, le temps tombe à 1.9s.
    En essayant de gérer un peu mieux le calcul des indices, j'arrive facilement à 1.5s et après quelques essais à 1.1s.

  3. #3
    Membre confirmé
    Homme Profil pro
    Collégien
    Inscrit en
    Mars 2003
    Messages
    192
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Afghanistan

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Mars 2003
    Messages : 192
    Par défaut
    Salut et merci de ta réponse !

    Je comprends que le code soit ralenti si le tableau ne tient pas en cache tout entier.

    En revanche, a quoi sert l'inversion de l'ordre des boucles dont tu parles ? Mes tableaux étant carrés (dans mon exemple) la dimension 'nx' a le même prix que la dimension 'ny', non ?

  4. #4
    Expert confirmé
    Avatar de diogene
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    Juin 2005
    Messages
    5 761
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2005
    Messages : 5 761
    Par défaut
    En revenant à une notation 2D ce qui amène le compilateur à faire lui même le calcul d'indexation sans rien changer sur le principe mais simplifie l'explication :

    On considère tab[i][j], l'élément tab[i][j+1] lui est voisin en mémoire et si tab[i][j] est en cache, le plus souvent, tab[i][j+1] le sera aussi.
    En modifiant le second indice, le cache aura besoin d'être mis à jour peu fréquemment.

    Par contre, l'élément tab[i+1][j] est éloigné de tab[i][j] par nx*sizeof(double) et si nx est assez grand, tab[i][j] peut être en cache et tab[i+1][j] ne pas l'être et nécessite un rechargement du cache.

    J'ai donc intérêt à effectuer le maximum d'opérations possibles en maintenant constant le premier indice pour réduire le va et vient des données au niveau du cache

  5. #5
    Membre confirmé
    Homme Profil pro
    Collégien
    Inscrit en
    Mars 2003
    Messages
    192
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Afghanistan

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Mars 2003
    Messages : 192
    Par défaut
    Citation Envoyé par diogene Voir le message
    Par contre, l'élément tab[i+1][j] est éloigné de tab[i][j] par nx*sizeof(double)
    ny tu veux dire ? 'ny' étant la dimension de l'indice 'j'. Il y a 'ny' double pour chaque 'i'.



    et si nx est assez grand, tab[i][j] peut être en cache et tab[i+1][j] ne pas l'être et nécessite un rechargement du cache.

    J'ai donc intérêt à effectuer le maximum d'opérations possibles en maintenant constant le premier indice pour réduire le va et vient des données au niveau du cache

    Bah c'est ce que je pensais faire, non ?

    Si je fais :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    for (i=0; i < nx; i++)
        for (j=0; j < ny; j++)
             tmp = tab[i][j] + tab[i][j+1] + tab[i+1][j]

    l'indice j va le plus rapidement, donc pour un 'i' constant je lis en mémoire beaucoup de 'j' qui sont déjà préchargés dans le cache ?


    Et si je fais (ce que tu conseille je crois ?)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    for (j=0; j < ny; j++)
        for (i=0; i < nx; i++)
            tmp = tab[i][j] + tab[i][j+1] + tab[i+1][j]

    l'indice 'i' varie maintenant le plus rapidement, donc là j'imagine des échanges de 'ny*sizeof(double)' incessants entre la ram et le cache ?

    Ou alors j'ai pas compris...

  6. #6
    Expert confirmé
    Avatar de diogene
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    Juin 2005
    Messages
    5 761
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2005
    Messages : 5 761
    Par défaut
    -
    ny tu veux dire ? 'ny' étant la dimension de l'indice 'j'. Il y a 'ny' double pour chaque 'i'.
    Si tu as tab[nx][ny] alors oui.
    Bah c'est ce que je pensais faire, non ?
    - Mais le code
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    for (i=1; i < nx-1; i ++)
        {
        for (j = 1; j < ny-1; j++)
            {
            ij  = (i  ) + (j  )*(nx);
    ....
    semblait dire que ton tableau est en tab[ny][nx] et l'adressage correspondre à tab[j][i] ce qui n'est peut-être pas ce que tu escomptais. La boucle interne (j) correspond à des incréments de nx éléments.

  7. #7
    Membre confirmé
    Homme Profil pro
    Collégien
    Inscrit en
    Mars 2003
    Messages
    192
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Afghanistan

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Mars 2003
    Messages : 192
    Par défaut
    Citation Envoyé par diogene Voir le message
    -
    Si tu as tab[nx][ny] alors oui.
    ok


    - Mais le code
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    for (i=1; i < nx-1; i ++)
        {
        for (j = 1; j < ny-1; j++)
            {
            ij  = (i  ) + (j  )*(nx);
    ....
    semblait dire que ton tableau est en tab[ny][nx] et l'adressage correspondre à tab[j][i] ce qui n'est peut-être pas ce que tu escomptais. La boucle interne (j) correspond à des incréments de nx éléments.
    effectivement, le tableau 2D correpondant au calcul :

    i + j*nx


    est un tab[ny][nx]...

    faire une boucle sur i, puis sur j, est donc stupide, je suis d'accord si c'est ça que tu dis ?

    Merci

  8. #8
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Heimdall Voir le message
    En revanche, a quoi sert l'inversion de l'ordre des boucles dont tu parles ? Mes tableaux étant carrés (dans mon exemple) la dimension 'nx' a le même prix que la dimension 'ny', non ?
    Citation Envoyé par Heimdall Voir le message
    faire une boucle sur i, puis sur j, est donc stupide, je suis d'accord si c'est ça que tu dis ?
    c'est une "feature" classique

    C'est la principale différence du point de vue du calcul entre Fortran et C

    Entre Fortran (lmathématique logique) et C (pointeurs), il faut inverser l'ordre d'accès à un élément d'une matrice..

    Tout simplement parce que les élements sont stockés dans un cas par colonne et dans l'autre par ligne (équivalent tableau 1D) ...


    Note : Cours Fortran

    Ordre des éléments

    En mémoire la notion de tableau n'existe pas : les éléments sont rangés les uns à la suite des autres.

    Pour accéder à ces éléments, dans l'ordre mémoire, Fortran fait d'abord varier le premier indice, puis le second et ainsi de suite.

  9. #9
    Membre confirmé
    Homme Profil pro
    Collégien
    Inscrit en
    Mars 2003
    Messages
    192
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Afghanistan

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Mars 2003
    Messages : 192
    Par défaut
    Salut,

    Ok... tu me crois si tu veux, mais je fais du C depuis longtemps, et ça je le savais, mais ça fait 3 ans que je travailles avec un code qui fait des boucles dans le mauvais sens sur ce genre de tableau 1D....

    dingue !

    Par contre, je n'ai jamais été un fan de l'apellation "ligne" et "colonne". Pour moi ça n'a aucun sens, une colonne c'est vertical et une ligne horizontale... et c'est tout ! Un tableau il y a un indice rapide et un lent.. est après ce qu'on appelle ligne ou colonne c'est une définition totalement arbitraire qui complique tout.


    Bon la conclusion de tout ça au final, hormi le fait que je vais inverser toutes les boucles de mon code, c'est que 1D ou 2D pour l'implémentation d'une grille on s'en balance un peu ? Peut-etre pour les machines vectorielles, l'implémentation 1D est meilleure..? sinon il y a d'autre arguments pour l'un ou pour l'autre ?

  10. #10
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Heimdall Voir le message
    Par contre, je n'ai jamais été un fan de l'apellation "ligne" et "colonne". Pour moi ça n'a aucun sens, une colonne c'est vertical et une ligne horizontale... et c'est tout ! Un tableau il y a un indice rapide et un lent.. est après ce qu'on appelle ligne ou colonne c'est une définition totalement arbitraire qui complique tout.

    mdr....

    ça c'est une appellation de geek..

    Mais quand on fait des maths (ce qui est en général l'utilisation des matrices), c'est bien appelé ligne ou colonne

  11. #11
    Membre confirmé
    Homme Profil pro
    Collégien
    Inscrit en
    Mars 2003
    Messages
    192
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Afghanistan

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Mars 2003
    Messages : 192
    Par défaut
    Citation Envoyé par souviron34 Voir le message
    mdr....

    ça c'est une appellation de geek..

    Mais quand on fait des maths (ce qui est en général l'utilisation des matrices), c'est bien appelé ligne ou colonne

    Bah oui je sais... je suis physicien donc je fais des maths parfois... mais le fait est qu'en parlant de tableau en programmation, ça n'a pas de sens de parler de column-major ou row-major... si tu ne précise pas ce que t'appelle une ligne et ce que t'appelle une colonne... on est obligé de faire un parallèle douteux entre la notation (arbitraire) matricelle a_{ij} et l'accès à un tableau a[i][j]... j'aime pas

  12. #12
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Heimdall Voir le message
    Bon la conclusion de tout ça au final, hormi le fait que je vais inverser toutes les boucles de mon code, c'est que 1D ou 2D pour l'implémentation d'une grille on s'en balance un peu ? Peut-etre pour les machines vectorielles, l'implémentation 1D est meilleure..? sinon il y a d'autre arguments pour l'un ou pour l'autre ?
    oui

    comme je l'ai dit dans l'autre post :

    si tu fais référence aux indices, c'est effectivement équivalent (4 opérations) :

    • dans un cas 2 * (1 multiplication et une addition) ([I]tab[j] nécessite de calculer adr1 = i*size + tab, puis adr = j*size + adr1)
    • dans l'autre cas c'est pareil : 1 multiplication (a1 = i*j), une addition (a2 = a1 + j), 1 multiplication (a = a2 * taille), et une addition (adr = tab + a)



    Par contre, si tu utilises un tableau 1D, et en utilisant un pointeur, si tu dois parcourir toute la matrice tu utilises seulement 1 addition pour chaque cellule
    (la taille n'est calculée qu'une fois par le compilateur à l'incrément). Et même si on la calculait à chaque fois, ça réduiait toujours d'un facteur 2..

  13. #13
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Heimdall Voir le message
    on est obligé de faire un parallèle douteux entre la notation (arbitraire) matricelle a_{ij} et l'accès à un tableau a[i][j]... j'aime pas
    Disons que si on utilises Fortran (qui a été fait pour les maths), on n'a pas à se poser de questions...

    Si on utilise un autre langage, c'est qu'ils ne se sont pas basés pour les maths, et ce sont eux qui ont biaisé le problème..

Discussions similaires

  1. [Perl 5.10.2] Tableau associatif à plusieurs dimensions
    Par Bahan_auboulot dans le forum Langage
    Réponses: 2
    Dernier message: 04/09/2008, 11h15
  2. Réponses: 2
    Dernier message: 06/09/2007, 15h08
  3. Réponses: 2
    Dernier message: 10/08/2007, 12h50
  4. Réponses: 5
    Dernier message: 03/06/2007, 14h07
  5. tableau a plusieurs dimensions envoyé par xhr.send
    Par kapfab dans le forum Général JavaScript
    Réponses: 1
    Dernier message: 07/03/2007, 16h24

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo