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

Je veux remettre à zéro à plusieurs reprises un grand tableau 2d en C.C'est ce que je fais pour le 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 baies 1D. Quand j'imprime le contenu du tableau 2D, la première ligne est des zéros, mais ensuite j'ai eu une charge de grands nombres aléatoires et ça plante.

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

Où met nsont la largeur et la hauteur du tableau à deux dimensions (dans votre exemple, vous avez un tableau carré à deux dimensions, donc m == n).

Si arrayest vraiment un tableau, alors vous pouvez le "remettre à zéro" avec:

memset(array, 0, sizeof array);

Mais il y a deux points que vous devez savoir:

• cela ne fonctionne que si arrayest vraiment un "tableau à deux d", c'est-à-dire a été déclaré T array[M][N];pour un type T.
• cela ne fonctionne que dans la portée où a arrayété déclaré. Si vous le passez à une fonction, le nom array se désintègre en pointeur et sizeofne 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 impressions 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

Même s'il arrs'agit d'un tableau, il se désintègre en un pointeur vers son premier élément lorsqu'il est passé à f(), et par conséquent, les tailles imprimées f()sont "incorrectes". En outre, 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" ne se produit qu'au premier niveau, et c'est pourquoi nous devons déclarer f()comme prenant un pointeur vers un tableau de taille correcte.

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 forboucle que vous avez postée ne sont pas équivalentes au sens strict. Il pourrait y avoir (et il y a eu) des compilateurs où «tous les bits à zéro» n'est pas égal à zéro pour certains types, tels que les pointeurs et les valeurs à virgule flottante. Je doute que vous ayez à vous en préoccuper.

Eh bien, le moyen le plus rapide de le faire est de ne pas le faire du tout.

Cela semble étrange, je sais, voici un 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 efface toujours le tableau, mais seulement lorsque quelque chose est écrit dans le tableau. Ce n'est pas un gros avantage ici. Cependant, si le tableau 2D a été implémenté en utilisant, par exemple, un quadruple arbre (pas un esprit dynamique) ou une collection de lignes de données, vous pouvez localiser l'effet du drapeau booléen, mais vous auriez besoin de plus d'indicateurs. Dans l'arbre quadruple, définissez simplement le drapeau vide pour le nœud racine, dans le tableau de lignes, définissez simplement le drapeau pour chaque ligne.

Ce qui conduit à la question "pourquoi voulez-vous remettre à zéro à plusieurs reprises un grand tableau 2D"? À quoi sert le tableau? Existe-t-il un moyen de modifier le code afin que le tableau ne nécessite pas de mise à zéro?

Par exemple, si vous aviez:

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

autrement dit, utilisez-le pour un tampon d'accumulation, puis le changer comme cela améliorerait les performances 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 d'effacer le tableau mais fonctionne toujours. Et ce sera beaucoup plus rapide que d'effacer le tableau. Comme je l'ai dit, le moyen le plus rapide est de ne pas le faire en premier lieu.

Si vous êtes vraiment, vraiment obsédé par la vitesse (et pas tant par la portabilité), je pense que le moyen le plus rapide de le faire serait d'utiliser les éléments intrinsèques du vecteur SIMD. 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 stockage mettra quatre entiers 32 bits à zéro en un seul coup.

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

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

// 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 existe également une variante _mm_storeuqui contourne le cache (c'est-à-dire que la remise à zéro du tableau ne polluera pas le cache) qui pourrait vous donner des avantages de performances secondaires dans certaines circonstances.

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

Si vous initialisez le tableau avec malloc, utilisez à la callocplace; il mettra à zéro votre tableau gratuitement. (Même performance évidemment que memset, juste moins de code pour vous.)

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

... au moins dans GCC 4.8.

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

Si c'est quelque chose comme:

int arr[20][30];

Vous pouvez le mettre à zéro en faisant:

memset(arr, sizeof(int)*20*30);

Utilisez calloc au lieu de malloc. calloc initialisera tous les champs à 0.

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

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

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.

(changez le type des pointeurs ptr et ptr1 si votre type de tableau est différent de 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]);

while(ptr < ptr1)
{
    *ptr++ = 0;
}

memset(array, 0, sizeof(int [n][n]));

Vous pouvez essayer ceci

int array[20,30] = {{0}};

Cela se produit car sizeof (array) vous donne la taille d'allocation de l'objet pointé par array . ( tableau est juste un pointeur vers la première ligne de votre tableau multidimensionnel). Cependant, vous avez alloué des tableaux j de taille i . Par conséquent, vous devez multiplier la taille d'une ligne, qui est retournée par sizeof (tableau) par 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 alloués statiquement. Pour un tableau alloué dynamiquement, vous écririez

size_t arrayByteSize = sizeof(int) * i * j; 
int *array = malloc(array2dByteSite);
bzero(array, arrayByteSize);