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

92

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.

Wir
źródło

Odpowiedzi:

177
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).

James McNellis
źródło
1
Wydaje się, że to nie działa. Otrzymuję komunikat „proces zwrócony -1073741819” na blokach kodu, co jest usterką seg, prawda?
Eddy
8
@Eddy: Pokaż nam deklarację tablicy.
GManNickG,
1
Założę się, że zawiesza się na innych liniach, a nie na memset, ponieważ wspomniałeś o awarii przy zerowaniu tylko jednego wiersza.
Blindy
3
Huh. Właśnie przetestowałem tablicę zadeklarowaną jako int d0=10, d1=20; int arr[d0][d1]i memset(arr, 0, sizeof arr);działała zgodnie z oczekiwaniami (gcc 3.4.6, skompilowane z -std=c99 -Wallflagami). Zdaję sobie sprawę, że „to działa na moim komputerze” oznacza bezczynny przysiad, ale memset(arr, 0, sizeof arr); powinienem był działać. sizeof arr powinien zwrócić liczbę bajtów używanych przez całą tablicę (d0 * d1 * sizeof (int)). sizeof array[0] * m * nnie poda prawidłowego rozmiaru tablicy.
John Bode,
4
@John Bode: Prawda, ale to zależy od sposobu uzyskania tablicy. Jeśli masz funkcję, która przyjmuje parametr int array[][10], to sizeof(array) == sizeof(int*)ponieważ rozmiar pierwszego wymiaru nie jest znany. OP nie określił, w jaki sposób uzyskano tablicę.
James McNellis,
79

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ć.

Alok Singhal
źródło
memset(array, 0, n*n*sizeof array[0][0]);Chyba masz na myśli m*nnie n*ntak?
Tagc
Co dziwne, wydaje się, że to nie działa z wartościami takimi jak 1 i 2, zamiast 0.
Ashish Ahuja,
memsetdziała na poziomie bajtów (znaków). Ponieważ 1albo 2nie mają te same bajty podstawowej reprezentacji, nie można tego zrobić z memset.
Alok Singhal
@AlokSinghal Może wskazać, że " intw twoim systemie jest 4 bajty" gdzieś przed minimalnym przykładem roboczym, aby czytelnik mógł łatwo obliczyć sumy.
71GA
9

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.

Skizz
źródło
Ciekawy alternatywny sposób spojrzenia na problem.
Beska
1
Nie jestem pewien, czy dodanie dodatkowego porównania / gałęzi dla każdego odczytu jest warte odroczenia inicjalizacji tablicy w tym przypadku (choć może być twoja). Jeśli tablica naprawdę jest tak duża, że ​​czas inicjalizacji stanowi poważny problem, może zamiast tego użyć skrótu.
tixxit
8

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

Jarrod Smith
źródło
5

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).

Ben Zotto
źródło
Czy jest to szybsze niż memset, jeśli chcę wielokrotnie wyzerować moją tablicę?
Eddy
calloc wyzeruje go raz, w czasie inicjalizacji i prawdopodobnie nie będzie szybsze niż wywołanie malloc, a następnie memset. Po tym jesteś sam i możesz po prostu użyć memset, jeśli chcesz go ponownie wyzerować. O ile twój zestaw nie jest naprawdę ogromny, perf nie jest tak naprawdę brane pod uwagę na żadnej rozsądnej maszynie.
Ben Zotto,
3

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

... przynajmniej w GCC 4.8.

Inżynier
źródło
2

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);
Pablo Santa Cruz
źródło
Użyłem tablicy char [10] [10]. Ale dostałem błąd: za mało argumentów, by działać jako „memset”, i memset(a, 0, sizeof(char)*10*10);dla mnie działa dobrze. , Jak to się stało?
Noufal
1

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

DUDE_MXP
źródło
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;
}

mack369
źródło
Twój kod będzie prawdopodobnie wolniejszy niż w memsetprzypadku typów znaków.
tofro
0
memset(array, 0, sizeof(int [n][n]));
swestrup
źródło
1
tablica [n] [n] jest rozmiarem 1 elementu tablicy, więc tylko pierwszy element tablicy zostanie zainicjowany.
EvilTeach
Ups. Masz rację. Miałem zamiar umieścić podpis typu w parach, a nie przeszukiwać tablicy. Naprawione.
swestrup
0

Możesz tego spróbować

int array[20,30] = {{0}};
Călin Calin
źródło
Dodaj więcej szczegółów
Marko Popovic
-2

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);
VoidPointer
źródło
Pierwsza część jest zła. Dla sizeofoperatora arrayjest wskaźnik (jeśli ogłoszono tablicy). Zobacz moją odpowiedź jako przykład.
Alok Singhal,