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

92

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.

Remolino
fuente

Respuestas:

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

James McNellis
fuente
1
No parece funcionar. Recibo 'proceso devuelto -1073741819' en bloques de código, que es una falla seg, ¿verdad?
Eddy
8
@Eddy: Muéstranos la declaración del arreglo.
GManNickG
1
Apuesto a que se está estrellando en otras líneas, no en la memset, porque mencionaste que también se bloquea por poner a cero solo una fila.
Blindy
3
¿Eh? Intenté probar una matriz declarada como int d0=10, d1=20; int arr[d0][d1]y memset(arr, 0, sizeof arr);funcionó como se esperaba (gcc 3.4.6, compilado con -std=c99 -Wallbanderas). Me doy cuenta de que "funciona en mi máquina" significa sentadilla, pero memset(arr, 0, sizeof arr); debería haber funcionado. sizeof arr debe devolver el número de bytes utilizados por toda la matriz (d0 * d1 * sizeof (int)). sizeof array[0] * m * nno le dará el tamaño correcto de la matriz.
John Bode
4
@John Bode: Cierto, pero depende de cómo se obtenga la matriz. Si tiene una función que toma un parámetro int array[][10], entonces, sizeof(array) == sizeof(int*)dado que no se conoce el tamaño de la primera dimensión. El OP no especificó cómo se obtuvo la matriz.
James McNellis
78

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.

Alok Singhal
fuente
memset(array, 0, n*n*sizeof array[0][0]);¿Supongo que te refieres a que m*nno n*n?
Tagc
Curiosamente, esto no parece funcionar con valores como 1 y 2, en lugar de 0.
Ashish Ahuja
memsetfunciona a nivel de bytes (char). Dado que 1o 2no tienen los mismos bytes en la representación subyacente, no puede hacer eso con memset.
Alok Singhal
@AlokSinghal Tal vez señale que " inten su sistema hay 4 bytes" en algún lugar antes del ejemplo de trabajo mínimo, para que el lector pueda calcular fácilmente las sumas.
71GA
9

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.

Skizz
fuente
Interesante forma alternativa de ver el problema.
Beska
1
No estoy seguro de que valga la pena agregar una comparación / rama adicional para cada lectura individual, y en este caso valga la pena aplazar la inicialización de la matriz (aunque puede ser la suya). Si la matriz realmente es tan grande que el tiempo de inicialización representa una seria preocupación, entonces podría usar un hash en su lugar.
tixxit
8

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

Jarrod Smith
fuente
5

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

Ben Zotto
fuente
¿Es esto más rápido que memset si quiero poner a cero repetidamente mi matriz?
Eddy
calloc lo pondrá a cero una vez, en el momento de la inicialización, y probablemente no será más rápido que llamar a malloc seguido de memset. Después de eso, estará solo y puede usar Memset si desea volver a ponerlo a cero. A menos que su matriz sea realmente enorme, el rendimiento no es realmente una consideración aquí en ninguna máquina razonable.
Ben Zotto
3

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

... al menos en GCC 4.8.

Ingeniero
fuente
2

¿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);
Pablo Santa Cruz
fuente
He usado una matriz char [10] [10]. Pero tengo un error: muy pocos argumentos para funcionar 'memset', y memset(a, 0, sizeof(char)*10*10);funciona bien para mí. , ¿Cómo sucede?
noufal
1

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

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

mack369
fuente
Lo más probable es que su código sea más lento que memsetpara los tipos de caracteres.
tofro
0
memset(array, 0, sizeof(int [n][n]));
swestrup
fuente
1
matriz [n] [n] es el tamaño de 1 elemento de la matriz, por lo tanto, solo se inicializaría el primer elemento de la matriz.
EvilTeach
¡Ups! Estás en lo correcto. Quería poner una firma de tipo en el parens, no una búsqueda de matriz. Arreglado.
swestrup
0

Puedes probar esto

int array[20,30] = {{0}};
Călin Calin
fuente
Agregue más detalles
Marko Popovic
-2

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);
VoidPointer
fuente
La primera parte está mal. Para el sizeofoperador, arrayno es un puntero (si se declaró una matriz). Vea mi respuesta como ejemplo.
Alok Singhal