¿La forma más rápida de poner a cero una matriz 2d en C?

Quiero poner a cero repetidamente una gran matriz 2d en C. Esto es lo que hago en este 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;
    }
}

Intenté usar memset:

memset(array, 0, sizeof(array))

Pero esto solo funciona para matrices 1D. Cuando imprimo el contenido de la matriz 2D, la primera fila son ceros, pero luego obtuve una carga de números grandes aleatorios y se bloquea.

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

Donde my nson el ancho y la altura de la matriz bidimensional (en su ejemplo, tiene una matriz bidimensional cuadrada, entonces m == n).

Si arrayes realmente una matriz, entonces puede "ponerla a cero" con:

memset(array, 0, sizeof array);

Pero hay dos puntos que debes conocer:

• esto funciona sólo si arrayes realmente una "matriz bidimensional", es decir, se declaró T array[M][N];para algún tipo T.
• funciona solo en el ámbito donde arrayfue declarado. Si lo pasa a una función, entonces el nombre se array convierte en un puntero y sizeofno le dará el tamaño de la matriz.

Hagamos un experimento:

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

En mi máquina, se imprime lo anterior:

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

Aunque arres una matriz, se convierte en un puntero a su primer elemento cuando se pasa a f(), y por lo tanto los tamaños impresos f()son "incorrectos". Además, en f()el tamaño de arr[0]es el tamaño de la matriz arr[0], que es una "matriz [5] de int". No es del tamaño de un int *, porque el "decaimiento" solo ocurre en el primer nivel, y es por eso que necesitamos declararf() como tomando un puntero a un arreglo del tamaño correcto.

Entonces, como dije, lo que estaba haciendo originalmente solo funcionará si se cumplen las dos condiciones anteriores. De lo contrario, deberá hacer lo que otros han dicho:

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

Finalmente, memset()y el forbucle que publicaste no son equivalentes en sentido estricto. Podría haber (y ha habido) compiladores donde "todos los bits cero" no es igual a cero para ciertos tipos, como punteros y valores de coma flotante. Sin embargo, dudo que tengas que preocuparte por eso.

Bueno, la forma más rápida de hacerlo es no hacerlo en absoluto.

Suena extraño, lo sé, aquí hay un pseudocódigo:

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 realidad, todavía está borrando la matriz, pero solo cuando se escribe algo en la matriz. Esto no es una gran ventaja aquí. Sin embargo, si la matriz 2D se implementó usando, digamos, un árbol cuádruple (no una mente dinámica), o una colección de filas de datos, entonces puede localizar el efecto de la bandera booleana, pero necesitaría más banderas. En el árbol cuádruple, simplemente configure la bandera vacía para el nodo raíz, en la matriz de filas simplemente configure la bandera para cada fila.

Lo que lleva a la pregunta "¿por qué quiere poner a cero repetidamente una matriz 2d grande"? ¿Para qué se utiliza la matriz? ¿Hay alguna forma de cambiar el código para que la matriz no necesite puesta a cero?

Por ejemplo, si tuvieras:

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

es decir, utilícelo para un búfer de acumulación, luego cambiarlo de esta manera mejoraría el rendimiento sin 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 

Esto no requiere que se borre la matriz, pero aún funciona. Y eso será mucho más rápido que borrar la matriz. Como dije, la forma más rápida es no hacerlo en primer lugar.

Si está realmente obsesionado con la velocidad (y no tanto con la portabilidad), creo que la forma más rápida de hacerlo sería usar los intrínsecos vectoriales SIMD. Por ejemplo, en CPU Intel, puede usar estas instrucciones 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.

Cada instrucción de almacenamiento establecerá cuatro entradas de 32 bits en cero en un solo golpe.

p debe estar alineado con 16 bytes, pero esta restricción también es buena para la velocidad porque ayudará a la caché. La otra restricción es que p debe apuntar a un tamaño de asignación que sea un múltiplo de 16 bytes, pero esto también es genial porque nos permite desenrollar el ciclo fácilmente.

Haga esto en un bucle y desenrolle el bucle unas cuantas veces, y tendrá un inicializador increíblemente rápido:

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

También hay una variante de _mm_storeu que evita la caché (es decir, poner a cero la matriz no contaminará la caché) lo que podría brindarle algunos beneficios secundarios de rendimiento en algunas circunstancias.

Consulte aquí para obtener una referencia de SSE2: http://msdn.microsoft.com/en-us/library/kcwz153a(v=vs.80).aspx

Si inicializa la matriz con malloc, use callocen su lugar; pondrá a cero su matriz de forma gratuita. (Obviamente, el mismo rendimiento que memset, solo que menos código para usted).

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

... al menos en GCC 4.8.

¿Cómo se declaró su matriz 2D?

Si es algo como:

int arr[20][30];

Puede ponerlo a cero haciendo:

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

Utilice calloc en lugar de malloc. calloc iniciará todos los campos a 0.

int * a = (int *) calloc (n, tamaño de (int));

// todas las celdas de a se han inicializado a 0

Creo que la forma más rápida de hacerlo a mano es siguiendo el código. Puede comparar su velocidad con la función de memset, pero no debería ser más lenta.

(cambie el tipo de punteros ptr y ptr1 si su tipo de matriz es diferente de 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]));

Puedes probar esto

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

Esto sucede porque sizeof (matriz) le da el tamaño de asignación del objeto al que apunta la matriz . (la matriz es solo un puntero a la primera fila de su matriz multidimensional). Sin embargo, asignó j matrices de tamaño i . En consecuencia, debe multiplicar el tamaño de una fila, que se devuelve por sizeof (matriz) con el número de filas que asignó, por ejemplo:

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

También tenga en cuenta que sizeof (matriz) solo funcionará para matrices asignadas estáticamente. Para una matriz asignada dinámicamente, escribiría

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