Moyen le plus rapide à zéro un tableau 2D en C?

Question

Je veux zéro à plusieurs reprises un grand tableau 2d C. Voici 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;
    }
}

Je l'ai essayé d'utiliser memset:

memset(array, 0, sizeof(array))

Mais cela ne fonctionne que pour les tableaux 1D. Quand je printf le contenu du tableau 2D, la première ligne est des zéros, mais je me suis une charge de nombres aléatoires grands et il se bloque.

Answer 1

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

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

Answer 2

Si array est vraiment un tableau, alors vous pouvez « zéro dehors » avec:

memset(array, 0, sizeof array);

Mais il y a deux points que vous devez savoir:

• cela ne fonctionne que si array est vraiment un "tableau à deux d", à savoir, a été déclaré T array[M][N]; pour certains T type.
• il ne fonctionne que dans le périmètre où array a été déclarée. Si vous passez à une fonction, le nom array désintègre à un pointeur et sizeof volonté 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 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 si arr est un tableau, il se désintègre à un pointeur sur son premier élément lorsqu'il est passé à f(), et par conséquent les tailles imprimées en f() sont « mauvais ». En outre, dans f() la taille de arr[0] est la taille de la arr[0] de réseau, qui est une « matrice [5] de int ». Il n'est pas la taille d'un int *, parce que le « pourrissement » ne se produit que au premier niveau, et qui est la raison pour laquelle nous devons déclarer f() que de prendre un pointeur sur un tableau de la taille correcte.

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

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

Enfin, memset() et la boucle de for vous avez publié ne sont pas équivalents au sens strict. Il pourrait y avoir (et ont été) compilateurs où « tous les bits zéro » ne zéro pas égal pour certains types, tels que les pointeurs et les valeurs à virgule flottante. Je doute que vous devez vous soucier que si.

Answer 3

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

Sons Je sais étrange, voici quelques pseudo-code:

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 encore le tableau de compensation, mais seulement quand quelque chose est écrit au tableau. Ce n'est pas un gros avantage ici. Cependant, si le tableau 2D a été mis en œuvre en utilisant, par exemple, un arbre quad (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 de drapeaux. Dans l'arbre de quad vient de mettre le drapeau vide pour le noeud racine, dans le réseau de rangées situé juste à l'indicateur pour chaque ligne.

Ce qui nous amène à la question « pourquoi voulez-vous à zéro à plusieurs reprises un grand tableau 2d »? Qu'est-ce que le tableau utilisé? Est-il possible de changer le code de sorte que le tableau n'a pas besoin de mise à zéro?

Par exemple, si vous avez:

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

qui est, pour l'utiliser 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 le tableau être résorbés, mais fonctionne toujours. Et ce sera beaucoup plus rapide que la compensation du tableau. Comme je l'ai dit, le meilleur moyen est de ne pas le faire en premier lieu.

Answer 4

Si vous êtes vraiment, vraiment obsédé par la vitesse (et non pas tant avec la portabilité) Je pense que l'absolu le plus rapide façon de le faire serait d'utiliser intrinsics 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 établira quatre 32 bits ints à zéro en un seul coup.

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

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

// 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 (à savoir la mise à zéro du tableau ne polluera pas le cache) qui pourrait vous donner des avantages de performance secondaires dans certaines circonstances.

Voir ici pour référence SSE2: http://msdn.microsoft. com / fr-fr / bibliothèque / kcwz153a (v = vs.80) .aspx

Answer 5

Si vous initialisez le tableau avec malloc, l'utilisation calloc au lieu; il zéro votre tableau gratuitement. (Même perf évidemment que memset, le code un peu moins pour vous.)

Answer 6

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

... au moins dans GCC 4.8.

Answer 7

Comment votre tableau 2D déclaré?

Si quelque chose comme:

int arr[20][30];

Vous pouvez le zéro en faisant:

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

Answer 8

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

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

// toutes les cellules d'un ont été initialisé à 0

Answer 9

Je pense que le meilleur moyen de le faire à la main est code suivant. Vous pouvez comparer sa vitesse à la fonction memset, mais il ne devrait pas être plus lent.

(changement de type de pointeurs ptr et ptr1 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]);

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

Answer 10

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

Answer 11

Vous pouvez essayer

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

Answer 12

Cela se produit parce que sizeof (tableau) vous donne la taille d'allocation de l'objet pointé par array . ( array est juste un pointeur vers la première ligne de votre tableau multidimensionnel). Cependant, vous avez alloué j tableaux de taille i . Par conséquent, il faut multiplier la taille d'une rangée, qui est renvoyé par sizeof (tableau) avec le nombre de lignes allouées, par exemple:.

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

Notez également que sizeof (tableau) ne fonctionne 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);