Matrices

Les matrices sont utiles pour simuler des echiquiers, des images “matricielles”, des problèmes linéaires… Ce sont des tableaux de tableaux qui peuvent ou non etre contigus en mémoire, les pointeurs sur VLA permettent dén créer vec une syntaxe très simple.

Matrice sur la pile

Pour adresser une case de matrice on enchaine les crochets ainsi : mat[10][20]. On déclare parillement une matrice sur la pile ainsi int mat[100][100] = {0}.

Matrices sur le tas avec N allocations

Mais il faut faire attention car les matrices onttendance a rapidement consommer de la memoire et il vaut mieux les alouer sur le tas via malloc. Une manière naïve de le faire est ainsi :


int main() {


    int mat ** = malloc(sizeof (int*) * 100);
    for int(i = 0 ; i < 100 ; i++) {
        mat[i] = malloc(sizeof (int) * 100);
        memset(&mat[i], sizeof (int) * 100, 0);
    }

    // on utilise la matrice

    // on "libère la matrice", attention de
    // le faire dns le bon ordre

    for int(i = 0 ; i < 100 ; i++) {
       free(mat[i]);
    }
    free(mat);

}

Avec une fonction qui “simplifie” le procédé on doit passer par une triple indirection


int create_mat(int *** mat, int cols, int rows)
{
    *mat = malloc(sizeof(int*) * rows);
    for (int i = 0; i < rows; i++) {
        (*mat)[i] = malloc(sizeof(int) * cols);
        memset(&mat[i], sizeof (int) * cols, 0);
    }

    return 0;
}

int free_mat(int *** mat, int rows)
{
    for int(i = 0 ; i < rows ; i++) {
       free((*mat)[i]);
    }
    free(*mat);

    return 0;
}

int main()
{
    int ** mat;
    create_mat(&mat, 100, 100);

    // ... travail avec la matrice

    free_mat(&mat, 100);

    return 0;
}

Le premier souci avec cette façon de faire est que vous voulez mettre toutes les valeurs de la matrice a zero il faut le faire ligne par ligne : il n’est pas possiblede la memset en un seul tenant car chaque ligne de la matrice est eparpillée en mémoire. Et au demeurant vous avez une allocation de m´émoire qui ne contient que des adresses vers des lignes et il ne faut pas memset ce “catalogue” sous peine de fuite de mémoire.

Matrice sur le tas avec 2 allocations

Une maniere d´éviter d’éparpiller la mémoire et d’alouer toutes les lignes et un seul bloc et d’avoir une deuxieme allocation pour le catalogue, puis de tricoter à la main le catlogue pour que chaque ligne pointe au bon endroit du bloc.

int create_mat(int *** mat, int cols, int rows)
{
    *mat = malloc(sizeof(int*) * rows);
    int *chunk = malloc(sizeof(int) * rows *cols);
    memset(chunk sizeof (int) * cols * rows, 0);
    for (int i = 0; i < rows; i++) {
        (*mat)[i] = &chunk[i] + i * sizeof(int) * rows;
    }

    return 0;
}

int free_mat(int *** mat)
{
    free((*mat)[0]); // la premiere ligne du catalogue pointe vers le "chunk"
    free(*mat);

    return 0;
}

Matrice sur le tas avec une seule allocation

Enfin on peut alouer le bloc et le catalogue en un seul tanant

int create_mat(int *** mat, int cols, int rows)
{
    *mat = malloc(sizeof(int*) * rows + sizeof(int) * rows *cols);
    int * chunck = mat + sizeof(int*) * rows;
    memset(chunk, sizeof (int) * cols * rows, 0);
    for (int i = 0; i < rows; i++) {
        (*mat)[i] = &chunk[i] + i * sizeof(int) * rows;
    }

    return 0;
}

int free_mat(int *** mat)
{
    free(*mat); // le free est simplifié

    return 0;
}

Le probleme des matrices cubiques et a n > 2 dimensions

Ces techniques permettent d’optimiser la fragmentation en mémoire des matrices mais quand il s’agit de traiter avec dea matrices cubiques ou a n dimensions (mat[10][20][40][10]...) on en arrive a des fonctions de création de matrices a quadruple, quintuple, etc. étoiles et autant de boucles for imbriquées et de possibles erreurs. En outre les tableaux de catalogues de pointeurs vers la prochaine dimension finissent pas occuper en mémoire presque autant de place que les données en elles-meme. A titre déxemple voilà à quoi ressemblerait une façon d’alouer une matrice à 4 dimensions avec la technique naïve

int create_mat(int ***** mat, int dim1, int dim2, int dim3, int dim4)
{
    *mat = malloc(sizeof(int***) * dim1);
    for (int i = 0; i < dim1; i++) {
        (*mat)[i] = malloc(sizeof(int**) * dim2);
        for(int j = 0; j < dim2 ; j++) {
            (*mat)[i][j] = malloc(sizeof(int*) * dim3);
            for(int k = 0; k < dim3; k++) {
                (*mat)[i][j][k] = malloc(sizeof(int) * dim4);
                memset(*mat)[i][j][k], sizeof(int) * dim4, 0);
            }
        }
    }

    return 0;
}

int free_mat(int ***** mat, int dim1, int dim2, int dim3)
{
    for int(i = 0 ; i < dim1 ; i++) {
        for(int j = 0; j < dim2; j++) {
            for(int k = 0; k < dim3; k++) {
                free((*mat)[i][j][k]);
            }
            free((*mat)[i][j]);
        }
        free((*mat)[i]);
    }
    free(*mat);

    return 0;
}

A titre d’exercice vous pouvez écrire les fonctions de creation et de liberation de matrices dans le cas de ue et deux allocations.

Matrices via pointeurs sur VLA

Les VLA permettent de créer des tableaux de taille dynamique sur la pile, mais il est également possible de déclarer des “pointeurs sur VLA” qui pointent sur des tableaux quón a alloué sur le tas via malloc.

Les VLA permettent d’une part de se passer d’une allocation de “catalogue”, de ne plus avoir de triples, quadriuples, quituples pointeurs, et conservent l´avantage d’une allocation unique.

Voici a quoi ressemble une allocation de matrice a 5 dimensions vie un “pointeur sur VLA”.


int main()
{
    int dim1, dim2, dim3, dim4, dim5;
    dim1 = 10; dim2 = 20; dim3 = 40; dim4 = 10; dim5 = 5;
    int (*mat)[dim1][dim2][dim3][dim4][dim5] = malloc(sizeof(int[dim1][dim2][dim3][dim4][dim5])); 
    // "sizeof" fonctionne avec les VLA donc on peut aussi ecrire
    // int (*mat)[dim1][dim2][dim3][dim4][dim5] = malloc(sizeof(*mat));
    memset(mat, sizeof(*mat), 0); // comme ici par exemple

    // ... travail avec la matrice

    free(mat);
}

Alouer une matrice de cette façon est trivial : il n’est plus nécessaire de dédier une fonction pour ça.

C++ : En C++, il n´y a ni VLA, ni pointeurs sur VLA, ainsi cette technique ne fonctionne pas. On prefere de toutes façons utiliser des vecteurs de vecteurs, voire des std::array imbriqués si la contiguïté en mémoire est importante. Si vous avez vraiment besoin de VLA en C++, vous pouvez compiler les fichiers qui les utisent en mode “langage C” : les compilateurs savent mélanger les deux langages .

References