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.
12 réponses
memset(array, 0, sizeof(array[0][0]) * m * n);
où m
et n
sont la largeur et la hauteur du tableau bidimensionnel (dans votre exemple, vous avez un tableau bidimensionnel carré, donc m == n
).
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 quelconqueT
. - il ne fonctionne que dans la portée où
array
a été déclaré. Si vous le passez à une fonction, alors le nomarray
se désintègre à un pointeur , etsizeof
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.
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.
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
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.)
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);
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
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"
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);