Najszybszy sposób na wyzerowanie macierzy 2D w C?

Chcę wielokrotnie wyzerować dużą tablicę 2d w C.To właśnie robię w tej chwili:

// 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;
    }
}

Próbowałem użyć memset:

memset(array, 0, sizeof(array))

Ale działa to tylko dla tablic 1D. Kiedy drukuję zawartość tablicy 2D, pierwszy wiersz to zera, ale potem mam mnóstwo losowych dużych liczb i ulega awarii.

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

Gdzie mi nsą szerokością i wysokością dwuwymiarowej tablicy (w twoim przykładzie masz kwadratową dwuwymiarową tablicę, więc m == n).

Jeśli arraynaprawdę jest tablicą, możesz ją wyzerować za pomocą:

memset(array, 0, sizeof array);

Ale są dwie kwestie, o których powinieneś wiedzieć:

• działa to tylko wtedy, gdy arraynaprawdę jest "tablicą dwuwymiarową", tj. została zadeklarowana T array[M][N];dla jakiegoś typu T.
• działa tylko w zakresie, w jakim arrayzostał zadeklarowany. Jeśli przekażesz to do funkcji, nazwa array rozpadnie się na wskaźnik i sizeofnie poda rozmiaru tablicy.

Zróbmy eksperyment:

#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;
}

Na moim komputerze powyższe wydruki:

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

Mimo że arrjest tablicą, po przekazaniu do jej pierwszego elementu rozpada się na wskaźnik f(), dlatego drukowane rozmiary f()są „niewłaściwe”. Również f()rozmiar arr[0]to rozmiar tablicy arr[0], która jest „tablicą [5] z int”. Nie jest to rozmiar an int *, ponieważ "zanikanie" ma miejsce tylko na pierwszym poziomie i dlatego musimy zadeklarować f()jako wskaźnik do tablicy o odpowiednim rozmiarze.

Tak więc, jak powiedziałem, to, co robiłeś pierwotnie, zadziała tylko wtedy, gdy dwa powyższe warunki są spełnione. Jeśli nie, będziesz musiał zrobić to, co powiedzieli inni:

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

Wreszcie, memset()a forpętla zostanie zaksięgowana nie są równoważne w sensie ścisłym. Mogłyby istnieć (i były) kompilatory, w których „wszystkie bity zero” nie są równe zeru dla pewnych typów, takich jak wskaźniki i wartości zmiennoprzecinkowe. Wątpię jednak, żebyś musiał się tym martwić.

Cóż, najszybszym sposobem na to jest w ogóle tego nie robić.

Brzmi dziwnie, wiem, oto pseudokod:

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;
}

Właściwie nadal czyści tablicę, ale tylko wtedy, gdy coś jest zapisywane w tablicy. Nie jest to duża zaleta. Jeśli jednak tablica 2D została zaimplementowana przy użyciu, powiedzmy, quad tree (nie dynamicznego jednego umysłu) lub zbioru wierszy danych, możesz zlokalizować efekt flagi boolowskiej, ale potrzebujesz więcej flag. W drzewie quad po prostu ustaw pustą flagę dla węzła głównego, w tablicy wierszy po prostu ustaw flagę dla każdego wiersza.

Co prowadzi do pytania „dlaczego chcesz wielokrotnie wyzerować dużą tablicę 2D”? Do czego służy tablica? Czy istnieje sposób na zmianę kodu, aby tablica nie wymagała zerowania?

Na przykład, jeśli miałeś:

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

to znaczy, użyj go jako bufora akumulacyjnego, a zmiana w ten sposób poprawi wydajność bez końca:

 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 

Nie wymaga to czyszczenia tablicy, ale nadal działa. A to będzie znacznie szybsze niż czyszczenie tablicy. Jak powiedziałem, najszybszym sposobem jest nie robienie tego w pierwszej kolejności.

Jeśli naprawdę masz obsesję na punkcie szybkości (i nie tak bardzo przenośności), myślę, że absolutnie najszybszym sposobem na to byłoby użycie wewnętrznych elementów wektora SIMD. np. na procesorach Intela możesz użyć tych instrukcji 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.

Każda instrukcja przechowywania ustawi cztery 32-bitowe wartości całkowite na zero za jednym trafieniem.

p musi być wyrównane do 16 bajtów, ale to ograniczenie jest również dobre dla szybkości, ponieważ pomoże pamięci podręcznej. Innym ograniczeniem jest to, że p musi wskazywać na rozmiar alokacji będący wielokrotnością 16 bajtów, ale jest to również fajne, ponieważ pozwala nam łatwo rozwinąć pętlę.

Zrób to w pętli i rozwiń pętlę kilka razy, a otrzymasz szalenie szybki inicjator:

// 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);
}

Istnieje również wariant, _mm_storeuktóry omija pamięć podręczną (tj. Wyzerowanie tablicy nie zanieczyszcza pamięci podręcznej), co w pewnych okolicznościach może dać dodatkowe korzyści w zakresie wydajności.

Zobacz tutaj, aby zapoznać się z referencjami SSE2: http://msdn.microsoft.com/en-us/library/kcwz153a(v=vs.80).aspx

Jeśli inicjalizujesz tablicę za pomocą malloc, użyj calloczamiast tego; wyzeruje twoją tablicę za darmo. (Oczywiście ta sama perfekcja co memset, tylko mniej kodu).

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

... przynajmniej w GCC 4.8.

Jak została zadeklarowana twoja tablica 2D?

Jeśli to coś takiego:

int arr[20][30];

Możesz to wyzerować, wykonując:

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

Użyj calloc zamiast malloc. calloc zainicjuje wszystkie pola do 0.

int * a = (int *) calloc (n, size of (int));

// wszystkie komórki a zostały zainicjowane na 0

Myślę, że najszybszym sposobem zrobienia tego ręcznie jest śledzenie kodu. Możesz porównać jego szybkość z funkcją memset, ale nie powinna być wolniejsza.

(zmień typ wskaźników ptr i ptr1, jeśli typ twojej tablicy jest inny niż 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]));

Możesz tego spróbować

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

Dzieje się tak, ponieważ sizeof (tablica) podaje rozmiar alokacji obiektu wskazywanego przez tablicę . ( tablica to po prostu wskaźnik do pierwszego wiersza wielowymiarowej tablicy). Jednak przydzielono j tablice o rozmiarze i . W związku z tym należy pomnożyć rozmiar jednego wiersza, który jest zwracany przez sizeof (tablicę) przez liczbę przydzielonych wierszy, np .:

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

Zauważ również, że sizeof (tablica) będzie działać tylko dla tablic przydzielonych statycznie. Dla tablicy alokowanej dynamicznie napisałbyś

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