modo più veloce per azzerare una matrice 2D in C?

Question

Voglio azzerare ripetutamente una vasta gamma 2d in C. Questo è quello che faccio in questo momento:

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

Ho provato con memset:

memset(array, 0, sizeof(array))

Ma questo funziona solo per gli array 1D. Quando sono printf i contenuti della matrice 2D, la prima riga è zeri, ma poi ho un carico di grandi numeri casuali e si blocca.

Answer 1

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

Dove m e n sono la larghezza e l'altezza della matrice bidimensionale (nel tuo esempio, si dispone di una piazza array bidimensionale, così m == n).

Answer 2

Se array è veramente un array, allora si può "zero fuori" con:

memset(array, 0, sizeof array);

Ma ci sono due punti si dovrebbe sapere:

• questo funziona solo se array è in realtà una "due-d serie", vale a dire, è stato dichiarato T array[M][N]; per un certo tipo T.
• funziona solo nell'area in cui è stato dichiarato array. Se si passa a una funzione, allora il nome array decade a un puntatore e sizeof volontà non vi darà la dimensione della matrice.

Facciamo un esperimento:

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

Sulla mia macchina, le stampe di cui sopra:

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

Anche se arr è un array, decade in un puntatore al suo primo elemento quando passato a f(), e quindi le dimensioni stampate in f() sono "sbagliato". Inoltre f() la dimensione del arr[0] è la dimensione della arr[0] matrice, che è un "array [5] di int". Non è la dimensione di un int *, perché la "decadente" avviene solo al primo livello, e per questo motivo è necessario dichiarare f() come prendere un puntatore a una matrice di dimensioni corrette.

Quindi, come ho detto, quello che stavi facendo in origine funziona solo se le due condizioni di cui sopra sono soddisfatte. In caso contrario, è necessario fare ciò che altri hanno detto:

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

Infine, memset() e il ciclo for che hai postato non sono equivalenti in senso stretto. Ci potrebbero essere (e sono stati) compilatori dove "tutti i bit zero" non è pari a zero per determinati tipi, come puntatori e valori in virgola mobile. Dubito che è necessario preoccuparsi di questo però.

Answer 3

Bene, il modo più veloce per farlo è di non farlo a tutti.

Sembra strano lo so, ecco qualche pseudocodice:

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

In realtà, è ancora cancellare la matrice, ma solo quando qualcosa è stato scritto alla matrice. Questo non è un grande vantaggio qui. Tuttavia, se la matrice 2D è stato implementato utilizzando, per esempio, un albero di quad (non una mente dinamica), o un insieme di righe di dati, allora si può localizzare l'effetto della bandiera booleano, ma avresti bisogno di più bandiere. Nella struttura quad appena impostato il flag vuoto per il nodo radice, nella matrice di righe appena impostato il flag per ogni riga.

Il che porta alla domanda "perché vuoi per azzerare ripetutamente una vasta gamma 2d"? Qual è la matrice usata per? C'è un modo per cambiare il codice in modo che l'array non ha bisogno di azzeramento?

Ad esempio, se si ha:

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

cioè, usarlo per un buffer di accumulo, quindi modificando in questo modo potrebbe migliorare le prestazioni senza fine:

 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 

Ciò non richiede l'array da cancellare, ma funziona ancora. E che sarà di gran lunga più veloce di compensazione della matrice. Come ho detto, il modo più veloce è quello di non farlo in primo luogo.

Answer 4

Se siete veramente, veramente ossessionato con la velocità (e non tanto con la portabilità) Credo che l'assoluto più veloce modo per farlo sarebbe quello di utilizzare SIMD intrinseche vettoriali. per esempio. su CPU Intel, è possibile utilizzare queste istruzioni 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.

Ogni istruzione negozio sarà fissato quattro interi a 32 bit a zero in un colpo solo.

p deve essere di 16 byte allineati, ma questa limitazione è anche un bene per la velocità perché aiuterà la cache. L'altra restrizione è che p deve puntare ad una dimensione di allocazione che è un multiplo di 16 byte, ma è troppo freddo perché ci permette di srotolare il ciclo facilmente.

hanno questo in un ciclo, e srotolare il ciclo un paio di volte, e si avrà un initialiser veloce pazzo:

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

Esiste anche una variante di _mm_storeu che bypassa la cache (cioè azzeramento la matrice non inquinare la cache) che potrebbe dare alcuni vantaggi prestazionali secondarie in alcune circostanze.

Vedi qui per SSE2 di riferimento: http://msdn.microsoft. com / it-it / library / kcwz153a (v = vs.80) aspx

Answer 5

Se si inizializza l'array con malloc, uso calloc invece; sarà azzerare l'array gratuitamente. (Stesso perf ovviamente come memset, poco meno codice per voi.)

Answer 6

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

... almeno in GCC 4.8.

Answer 7

Come è stata la matrice 2D dichiarato?

Se è qualcosa di simile a:

int arr[20][30];

È possibile azzerare esso facendo:

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

Answer 8

Usa calloc invece di malloc. calloc avvierà tutti i campi a 0.

int * a = (int *) calloc (n, dimensione (int));

// tutte le cellule di un sono stati inizializzato a 0

Answer 9

Credo che il modo più veloce per farlo a mano è seguente codice. È possibile confrontare la sua velocità alla funzione memset, ma non dovrebbe essere più lento.

(tipo cambio di PTR e ptr1 puntatori se il tipo di matrice è diversa allora 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

Si può provare questo

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

Answer 12

Ciò accade perché sizeof (array) fornisce la dimensione di allocazione dell'oggetto puntato da array . ( array è solo un puntatore alla prima riga della matrice multidimensionale). Tuttavia, è assegnato j array di dimensioni i . Di conseguenza, è necessario moltiplicare le dimensioni di una riga, che viene restituito da sizeof (array) con il numero di righe allocato, per esempio:.

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

Si noti inoltre che sizeof (array) funziona solo per gli array allocati staticamente. Per un array allocato dinamicamente si può scrivere

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