Le moyen le plus rapide de mettre à zéro un tableau 2d en C?

je veux à plusieurs reprises zéro un grand tableau 2d en C. C'est ce que je fais en ce moment:

// Array of size n * m, where n may not equal m
for(j = 0; j < n; j++)
{
    for(i = 0; i < m; i++)
    {  
        array[i][j] = 0;
    }
}

j'ai essayé d'utiliser memset:

memset(array, 0, sizeof(array))

mais cela ne fonctionne que pour les matrices 1D. Quand j'imprime le contenu du tableau 2D, la première ligne est des zéros, mais ensuite j'ai une charge de grands nombres aléatoires et il se brise.

79
demandé sur Csaba Toth 2010-03-25 16:57:20

12 réponses

memset(array, 0, sizeof(array[0][0]) * m * n);

m et n sont la largeur et la hauteur du tableau bidimensionnel (dans votre exemple, vous avez un tableau bidimensionnel carré, donc m == n ).

156
répondu James McNellis 2010-03-25 14:46:00

Si array est vraiment un tableau, alors vous pouvez "zéro" avec:

memset(array, 0, sizeof array);

mais il y a deux points que vous devez savoir:

  • cela ne fonctionne que si array est réellement un "tableau BI-d", c'est-à-dire qu'il a été déclaré T array[M][N]; pour un type quelconque T .
  • il ne fonctionne que dans la portée où array a été déclaré. Si vous le passez à une fonction, alors le nom array se désintègre à un pointeur , et sizeof ne vous donnera pas la taille du tableau.

faisons une expérience:

#include <stdio.h>

void f(int (*arr)[5])
{
    printf("f:    sizeof arr:       %zu\n", sizeof arr);
    printf("f:    sizeof arr[0]:    %zu\n", sizeof arr[0]);
    printf("f:    sizeof arr[0][0]: %zu\n", sizeof arr[0][0]);
}

int main(void)
{
    int arr[10][5];
    printf("main: sizeof arr:       %zu\n", sizeof arr);
    printf("main: sizeof arr[0]:    %zu\n", sizeof arr[0]);
    printf("main: sizeof arr[0][0]: %zu\n\n", sizeof arr[0][0]);
    f(arr);
    return 0;
}

sur ma machine, les tirages ci-dessus:

main: sizeof arr:       200
main: sizeof arr[0]:    20
main: sizeof arr[0][0]: 4

f:    sizeof arr:       8
f:    sizeof arr[0]:    20
f:    sizeof arr[0][0]: 4
f() même si arr est un tableau, il se décompose en un pointeur vers son premier élément quand passé à f() , et donc les tailles imprimées dans f() sont"erroné". En outre, dans f() la taille de arr[0] est la taille du tableau arr[0] , qui est un "tableau [5] de int ". Ce n'est pas la taille d'un int * , parce que la "décomposition" n'arrive qu'au premier niveau, et c'est pourquoi nous avons besoin de déclarer f() un pointeur vers un tableau de la bonne taille.

donc, comme je l'ai dit, ce que vous faisiez à l'origine ne fonctionnera que si les deux conditions ci-dessus sont remplies. Sinon, vous devrez faire ce que les autres ont dit:

memset(array, 0, m*n*sizeof array[0][0]);

enfin, memset() et la boucle for que vous avez postée ne sont pas équivalentes au sens strict. Il pourrait y avoir (et il y a déjà eu) des compilateurs où "tous les bits zéro" n'est pas égal à zéro pour certains types, comme les pointeurs et les valeurs à virgule flottante. Je doute que vous ayez besoin de vous en inquiéter.

70
répondu Alok Singhal 2018-02-17 04:24:12

eh Bien, la façon la plus rapide de le faire est de ne pas le faire du tout.

semble étrange je sais, voici un certain pseudocode:

int array [][];
bool array_is_empty;


void ClearArray ()
{
   array_is_empty = true;
}

int ReadValue (int x, int y)
{
   return array_is_empty ? 0 : array [x][y];
}

void SetValue (int x, int y, int value)
{
   if (array_is_empty)
   {
      memset (array, 0, number of byte the array uses);
      array_is_empty = false;
   }
   array [x][y] = value;
}

en fait, il est toujours en train de nettoyer le tableau, mais seulement quand quelque chose est écrit sur le tableau. Ce n'est pas un grand avantage ici. Cependant, si le tableau 2D a été implémenté en utilisant, par exemple, un arbre quadrilatéral (pas un esprit dynamique), ou une collection de rangées de données, alors vous pouvez localiser l'effet du drapeau booléen, mais vous besoin de plus de drapeaux. Dans l'arbre des quadrilatères, il suffit de définir le drapeau vide pour le noeud racine, dans le tableau des lignes, il suffit de définir le drapeau pour chaque ligne.

ce qui amène à la question"Pourquoi voulez-vous à plusieurs reprises zéro un grand tableau 2d"? Qu'est-ce que la matrice? Y a-t-il un moyen de changer le code pour que le tableau n'ait pas besoin de mise à zéro?

par exemple, si vous aviez:

clear array
for each set of data
  for each element in data set
    array += element 

c'est-à-dire l'utiliser pour un tampon d'accumulation, puis le changer comme ceci améliorerait la performance sans fin:

 for set 0 and set 1
   for each element in each set
     array = element1 + element2

 for remaining data sets
   for each element in data set
     array += element 

cela ne nécessite pas que le tableau soit effacé mais fonctionne quand même. Et ce sera beaucoup plus rapide que de nettoyer le tableau. Comme je l'ai dit, le moyen le plus rapide est de ne pas le faire en premier lieu.

9
répondu Skizz 2010-03-25 14:18:21

si vous êtes vraiment, vraiment obsédé par la vitesse (et pas tellement avec la portabilité) je pense que l'absolu le plus rapide façon de le faire serait D'utiliser IMD vecteur intrinsèques. par exemple, sur les processeurs Intel, vous pouvez utiliser ces instructions SSE2:

__m128i _mm_setzero_si128 ();                   // Create a quadword with a value of 0.
void _mm_storeu_si128 (__m128i *p, __m128i a);  // Write a quadword to the specified address.

chaque instruction de magasin définira quatre ints de 32 bits à zéro en un coup.

p doit être aligné de 16 octets, mais cette restriction est également bonne pour la vitesse, car elle aidera le cache. L'autre limite est que p doit pointer vers une répartition de taille qui est un multiple de 16 octets, mais c'est trop cool parce qu'il nous permet de dérouler la boucle facilement.

ont ceci dans une boucle, et déroulez la boucle quelques fois, et vous aurez un initialiseur rapide fou:

// Assumes int is 32-bits.
const int mr = roundUpToNearestMultiple(m, 4);      // This isn't the optimal modification of m and n, but done this way here for clarity.    
const int nr = roundUpToNearestMultiple(n, 4);    

int i = 0;
int array[mr][nr] __attribute__ ((aligned (16)));   // GCC directive.
__m128i* px = (__m128i*)array;
const int incr = s >> 2;                            // Unroll it 4 times.
const __m128i zero128 = _mm_setzero_si128();

for(i = 0; i < s; i += incr)
{
    _mm_storeu_si128(px++, zero128);
    _mm_storeu_si128(px++, zero128);
    _mm_storeu_si128(px++, zero128);
    _mm_storeu_si128(px++, zero128);
}

il y a aussi une variante de _mm_storeu qui contourne le cache (c'est-à-dire que le zérotage du tableau ne polluera pas le cache) qui pourrait vous donner une certaine secondaire avantages liés au rendement dans certaines circonstances.

voir ici pour SSE2 référence: http://msdn.microsoft.com/en-us/library/kcwz153a (v = 80).aspx

7
répondu Jarrod Smith 2012-10-23 22:44:53

si vous initialisez le tableau avec malloc , utilisez calloc à la place; il va zéro votre tableau gratuitement. (Même perf évidemment que memset, juste moins de code pour vous.)

5
répondu Ben Zotto 2010-03-25 14:52:19

int array[N][M] = {0};

... au moins dans GCC 4.8.

3
répondu Arcane Engineer 2015-01-27 17:59:20

comment votre tableau 2D a-t-il été déclaré?

si c'est quelque chose comme:

int arr[20][30];

Vous pouvez zéro en faisant:

memset(arr, sizeof(int)*20*30);
2
répondu Pablo Santa Cruz 2010-03-25 14:00:40

utilisez calloc au lieu de malloc . calloc initiera tous les champs à 0.

int *a = (int *)calloc(n,la taille de l'(int)) ;

/ / toutes les cellules de a ont été initialisées à 0

1
répondu DUDE_MXP 2016-07-20 07:01:18

je pense que le moyen le plus rapide de le faire à la main est de suivre le code. Vous pouvez comparer sa vitesse à la fonction memset, mais elle ne devrait pas être plus lente.

(changement de type de ptr et ptr1 pointeurs si votre type de tableau est différent alors int)


#define SIZE_X 100
#define SIZE_Y 100

int *ptr, *ptr1;
ptr = &array[0][0];
ptr1 = ptr + SIZE_X*SIZE_Y*sizeof(array[0][0]);

"151910920"

0
répondu mack369 2010-03-25 16:53:14
memset(array, 0, sizeof(int [n][n]));
0
répondu swestrup 2012-08-24 15:11:14

vous pouvez essayer ceci

int array[20,30] = {{0}};
0
répondu Călin Calin 2016-04-19 19:27:18

cela se produit parce que sizeof(array) vous donne la taille d'attribution de l'objet pointé par array . ( array n'est qu'un pointeur vers la première ligne de votre array multidimensionnel). Cependant, vous avez attribué j tableaux de taille i . Par conséquent, vous devez multiplier la taille d'une ligne, qui est retournée par size of (array) avec le nombre de lignes que vous avez allouées, par exemple:

bzero(array, sizeof(array) * j);

notez également que sizeof(array) ne fonctionnera que pour les tableaux statiquement alloués. Pour un tableau alloué dynamiquement vous écririez

size_t arrayByteSize = sizeof(int) * i * j; 
int *array = malloc(array2dByteSite);
bzero(array, arrayByteSize);
-2
répondu VoidPointer 2010-03-25 14:11:47