Tableau en C

Moloch · Juillet 4, 2006, 3:47

Sinon tu peux te coder des tableaux dynamiques…

Drealmer · Juillet 4, 2006, 4:19

Pour plus d’informations, voici un excellent article sur assert : http://www.gamesfromwithin.com/articles/0510/000101.html

Maverick · Juillet 4, 2006, 5:15

Oui je sais, mais cela ne m’est d’aucune utilité dans mon cas, la taille est fixe.

Azhag · Juillet 4, 2006, 5:56

Ben je crois justement que non dans ton cas :

Si tu as un tableau dont la taille dépend d’une variable (que tu trouve depuis la ligne de commande, un fichier où je ne sais quoi), faut faire un tableau dynamique et te faire chier avec des mallocs.

Si je comprends bien ton exemple, tu récupère ces tailles depuis des fichiers, donc elles sont variables. En C t’es autorisé à faire des tableaux que de taille fixe (donc connue lorsque tu compiles).

Parce que c’est très possible que tu te tape un débordement d’indice parce que le compilo sun alloue les tableaux bizarrement.

Ou alors tu te la joues à la bourrin, et t’alloue un tableau de 100 000 lignes, tel le codeur moche d’opengl. B) (mais bon hein, c’est pas pro)

Maverick · Juillet 5, 2006, 2:01

[quote=“Azhag, post:24, topic: 29796”]Ben je crois justement que non dans ton cas :

Si tu as un tableau dont la taille dépend d’une variable (que tu trouve depuis la ligne de commande, un fichier où je ne sais quoi), faut faire un tableau dynamique et te faire chier avec des mallocs.

Si je comprends bien ton exemple, tu récupère ces tailles depuis des fichiers, donc elles sont variables. En C t’es autorisé à faire des tableaux que de taille fixe (donc connue lorsque tu compiles).

Parce que c’est très possible que tu te tape un débordement d’indice parce que le compilo sun alloue les tableaux bizarrement.

Ou alors tu te la joues à la bourrin, et t’alloue un tableau de 100 000 lignes, tel le codeur moche d’opengl. B) (mais bon hein, c’est pas pro)[/quote]
Oui mais ca malloc c’est depuis le deuxième post que ca en parle. Je pense (j’espère) qu’il parlait de vecteur dynamique avec realloc.

vectra · Juillet 5, 2006, 9:36

Je crois aussi. Alors, ca en est où??

Maverick · Juillet 6, 2006, 3:55

Alors j’ai remplacé toutes les définitions de matrices/vecteurs par une allocation de mémoire dynamique (et il y en avait un paquet!!) :

int matrice [nombre_x][nombre_y];

devient donc

int** matrice = (int**) NULL;

…

matrice = (int**) malloc(nombre_xsizeof(int));
if(matrice == (int**) NULL){
printf(« erreur allocation matrice\n »);
exit(EXIT_FAILURE);
}
for(i=0; i<nombre_x; i++){
matrice[i] = (int*) malloc(nombre_ysizeof(int));
if(matrice[i] == (int) NULL){
printf(« erreur allocation matrice ligne %d\n », i);
exit(EXIT_FAILURE);
}
}

voilà, ca passe sur les sun now. Merci pour l’aide, bisoux à tout le monde.

GloP · Juillet 6, 2006, 4:09

Perso, selon la maniere dont tu l’utilise, je trouve que ca serait peut etre mieux si ta matrice, meme en 2D, etait en un seul morceau, sous forme de struct par exemple. Un malloc avec un sizeof(int*), comme ca, c’est heu… bizzare pour mon noeil on va dire B)

vectra · Juillet 6, 2006, 9:30

B) Je comprends pas bien…
Ca me paraît plutôt proche de la forme normale, non?

Maverick · Juillet 6, 2006, 1:49

Mais encore ?

J’avais aussi fait un vecteur (nombre_xnombre_ysizeof(int)). Mais je trouve moins propre pour les accès.

vectra · Juillet 6, 2006, 8:40

[quote=“Maverick, post:30, topic: 29796”]Mais encore ?

J’avais aussi fait un vecteur (nombre_xnombre_ysizeof(int)). Mais je trouve moins propre pour les accès.[/quote]

C’est vrai que tu remplaces un des accès mémoire par une opération arithmétique, qui s’exécute bien plus vite AMHA. Si c’est pour une question de beauté syntaxique, p’tet bien qu’une macro genre ELEM(tab, i, j) -> elem[i * j] pourrait faire l’affaire (attention qd meme).

Le problème, c’est quand les tableaux sont grands: tu risques de ne plus pouvoir allouer le vecteur (ne rigolez pas, j’ai déjà vu un bourrin y arriver). Je pense surtout que c’est la pagination de l’OS qui va commencer à souffrir à ce moment-là, mais la, je commence à sécher.

Drealmer · Juillet 6, 2006, 8:50

Non, c’est idem. Les tableaux à plusieur dimensions sont contigus en C, il suffit d’un seul accès mémoire pour y accéder, y’a pas d’indirection.

JDaM · Juillet 7, 2006, 8:01

Je pense que ce qui pique l’oeil du monsieur c’est ça :

matrice = (int**) malloc(nombre_x*sizeof(int*));

Or pourtant c’est la forme logique puisqu’on alloue un tableau qui contenir les adresses
des autres tableaux, une matrice quoi…

Mais le problème c’est que cette opération est très couteuse en temps de calcul puisquelle
effectue n+1 mallocs.

Pour faire ça il existe une ruse de sioux très sympatique :

[code]// On reserve un tableau long de y pour les adresses
matrice = (int**) malloc(nombre_ysizeof(int));
// On reserve un tableau long de xy pour les elements
matrice = (int) malloc(nombre_xnombre_y*sizeof(int));

for(i=1;i<nombre_y;i++)
matrice[i] = matrice + inombre_xsizeof(int);

free(*matrice);
free(matrice);[/code]

En gros tu mets à la suite les lignes de ta matrice puis tu fais pointer ton tableau d’adresses dans les bonnes cases.

Si tu piges pas je peux en tartiner plus B)

PS: Le code si dessus à été valgrindé sans erreurs donc je pense qu’il devrait marcher sans fuites de mem…

Edit : orthographe

Drealmer · Juillet 7, 2006, 8:07

J’aime bien ta proposition Ceci dit, l’accès au tableau sera plus lent, car pour atteindre un élément, y’aura deux fetch au lieu d’un seul. M’enfin bon, c’est du chipotage.

JDaM · Juillet 7, 2006, 8:45

J’ai été obligé d’utiliser cette méthode alors que j’utilisais des grosses matrices bien carrés et que faire
10001 mallocs mine de rien ça prend du temps.

Drealmer · Juillet 7, 2006, 8:58

[quote=“JDaM, post:35, topic: 29796”]J’ai été obligé d’utiliser cette méthode alors que j’utilisais des grosses matrices bien carrés et que faire
10001 mallocs mine de rien ça prend du temps. B)[/quote]
Ben si tu dois stocker une matrice 100 x 100, t’as deux options. Soit ta méthode, soit un tableau de 10000 éléments. Niveau utilisation, avec ton système c’est plus agréable, car pour atteindre l’élément (x,y), on peut simplement écrire “matrix[x][y]”, alors qu’avec un seul gros tableau, on doit faire “matrix[x + y * 100]”. Niveau performances, la deuxième version est meilleure, car on a une multiplication, une addition, et un accès mémoire. Alors que dans la première version on a une addition, un accès mémoire, une addition, un accès mémoire. Et les accès mémoire sont très lents comparés à une opération arithmétique. Surtout si la matrice est grande et ne tient pas dans le cache.

JDaM · Juillet 7, 2006, 10:02

En effet oui, c’est pas faux tout ça… B)
J’y penserais la prochaine fois que j’aurais du code dans ce genre là…

Maverick · Juillet 7, 2006, 2:26

int matrice [nombre_x][nombre_y];

devient donc

int** matrice = (int**) NULL;

…

matrice = (int**) malloc(nombre_xsizeof(int));
if(matrice == (int**) NULL){
printf(“erreur allocation matrice\n”);
exit(EXIT_FAILURE);
}
for(i=0; i<nombre_x; i++){
matrice[i] = (int*) malloc(nombre_ysizeof(int));
if(matrice[i] == (int) NULL){
printf(“erreur allocation matrice ligne %d\n”, i);
exit(EXIT_FAILURE);
}
}

pour la libération mémoire je fais :

for(i=0; i<nombre_x; i++){
free((void*)matrice[i]);
matrice[i] = (int*) NULL;
}
free((void*) matrice);
matrice = (int**) NULL;

C’est correct ?

JDaM · Juillet 8, 2006, 9:53

Pour ce qui est de la libération de la mémoire le code est correct et ne devrait pas laisser de mémoire allouée.
Par contre je conseille fortement d’utiliser la technique que j’ai exposé plus haut ou celle de Drealmer si tu as à allouer des matrices de bonnes tailles ou si la rapidité de ton code est une chose importante.

Pour résumer si tu veux avoir un accès normal à la matrice (m[x][y]) utilise ma méthode et si tu veux avoir de très bonnes perfs utilise celle de Drealmer et accède à ta matrice par m[ x+y*nombre_x ].

Ah oui sinon, pour toutes ces histoires de problème de mémoire je conseille très fortement l’utilisation de ce petit bijou qu’est Valgrind.

http://valgrind.org/

Gratuit, libre et dans toutes les bonnes crêmeries unix.
( Je ne sais pas si il existe un équivalent Windows )

Moloch · Juillet 9, 2006, 10:06

[quote=“JDaM, post:39, topic: 29796”]Ah oui sinon, pour toutes ces histoires de problème de mémoire je conseille très fortement l’utilisation de ce petit bijou qu’est Valgrind.

http://valgrind.org/

Gratuit, libre et dans toutes les bonnes crêmeries unix.
( Je ne sais pas si il existe un équivalent Windows )[/quote]

[quote=“JDaM, post:39, topic: 29796”]Ah oui sinon, pour toutes ces histoires de problème de mémoire je conseille très fortement l’utilisation de ce petit bijou qu’est Valgrind.

http://valgrind.org/

Gratuit, libre et dans toutes les bonnes crêmeries unix.
( Je ne sais pas si il existe un équivalent Windows )[/quote]

Sous Windows il existe un outil très puissant qui se nomme Boundschecker qui offre un nombre incroyable de possibilités de vérifications. Par rapport à Valgrind ça offre plus de vérifications et c’est beaucoup plus convivial mais c’est aussi euh pas le même prix… B)

Do you want to know more?

Valgrind reste très bien sous Unix, je m’en sers systématiquement.

Sinon personellement j’utiliserais plutôt une approche de ce type pour coder ton problème (si j’ai bien compris) :

Cette solution ne fait que deux allocations mémoire quelle que soit la taille du tableau et te garantit une mémoire continue ce qui est intéressant en termes de performances (proche de celle de Dreamler donc). Si les tableaux deviennent trop grand et à trous, tu as interêt alors à rebasculer sur une solution à base “d’une allocation par blocs d’élements” en jouant sur le reserve/commit de mémoire virtuelle. C’est dommage que tu doives le faire en C, car en C++ il y avait moyen de faire quelque chose de plus joli.

[code]#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <memory.h>

typedef unsigned long matrix_atom;

struct SMatrix
{
matrix_atom *pMatrix;
size_t lXSize;
size_t lYSize;
};

SMatrix *AllocateMatrix(size_t lXSize, size_t lYSize)
{
assert(lXSize > 0);
assert(lYSize > 0);

SMatrix *pmxTemp = (SMatrix *)malloc(sizeof(SMatrix));
if (!pmxTemp)
	return NULL;

size_t lMatrixSize = lXSize * lYSize * sizeof(matrix_atom);
pmxTemp->pMatrix = (matrix_atom *)malloc(lMatrixSize);
if (!pmxTemp->pMatrix)
{
	free(pmxTemp);
	return NULL;
}

memset(pmxTemp->pMatrix, 0, lMatrixSize);

pmxTemp->lXSize = lXSize;
pmxTemp->lYSize = lYSize;


return pmxTemp;

}

size_t ComputeOffset(SMatrix *pMatrix, size_t x, size_t y)
{
assert(pMatrix != NULL);
assert(pMatrix->lXSize > x);
assert(pMatrix->lYSize > y);
return (pMatrix->lXSize * y) + x;
}

matrix_atom GetElement(SMatrix *pMatrix, size_t x, size_t y)
{
return pMatrix->pMatrix[ComputeOffset(pMatrix, x, y)];
}

void SetElement(SMatrix *pMatrix, size_t x, size_t y, matrix_atom atmValue)
{
pMatrix->pMatrix[ComputeOffset(pMatrix, x, y)] = atmValue;
assert(GetElement(pMatrix, x, y) == atmValue);
}

void FreeMatrix(SMatrix **ppMatrix)
{
if (!ppMatrix | !*ppMatrix)
return;

assert((*ppMatrix)->pMatrix != NULL);
free((*ppMatrix)->pMatrix);
free(*ppMatrix);
*ppMatrix = NULL;

}

int main(int argc, char **argv, char *envp)
{

SMatrix *pmxTest = AllocateMatrix(16, 16);
assert(pmxTest != NULL);

matrix_atom atmCounter = 0;

for(size_t x = 0; x < pmxTest->lXSize; x++)
{
	for(size_t y = 0; y < pmxTest->lYSize; y++)
	{
		SetElement(pmxTest, x, y, atmCounter++);
	}
}

atmCounter = 0;

for(size_t y = 0; y < pmxTest->lYSize; y++)
{
	for(size_t x = 0; x < pmxTest->lXSize; x++)
	{
		assert(GetElement(pmxTest, x, y) == (x * pmxTest->lYSize) + y);
	}
}

FreeMatrix(&pmxTest);

assert(pmxTest == NULL);

}[/code]