Maneira mais rápida de zerar uma matriz 2d em C?

92

Quero zerar repetidamente um grande array 2d em C. Isto é o que faço no 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;
    }
}

Tentei usar o memset:

memset(array, 0, sizeof(array))

Mas isso só funciona para arrays 1D. Quando imprimo o conteúdo da matriz 2D, a primeira linha é zeros, mas depois recebo uma carga de números grandes aleatórios e ela trava.

Eddy
fonte

Respostas:

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

Onde me nsão a largura e a altura da matriz bidimensional (em seu exemplo, você tem uma matriz bidimensional quadrada, portanto m == n).

James McNellis
fonte
1
Não parece funcionar. Recebo 'processo retornado -1073741819' em codeblocks, que é uma falha de seg, certo?
Eddy
8
@Eddy: Mostra-nos a declaração do array.
GManNickG
1
Aposto que está travando em outras linhas, não no memset, porque você mencionou travar por zerar apenas uma linha também.
Blindy
3
Hã. Acabei de tentar um teste com um array declarado como int d0=10, d1=20; int arr[d0][d1]e memset(arr, 0, sizeof arr);funcionou como esperado (gcc 3.4.6, compilado com -std=c99 -Wallsinalizadores). Eu percebo que "funciona na minha máquina" significa agachamento diddly, mas memset(arr, 0, sizeof arr); deveria ter funcionado. sizeof arr deve retornar o número de bytes usados ​​por toda a matriz (d0 * d1 * sizeof (int)). sizeof array[0] * m * nnão fornecerá o tamanho correto da matriz.
John Bode,
4
@John Bode: Verdadeiro, mas depende de como o array é obtido. Se você tem uma função que leva um parâmetro int array[][10], então, sizeof(array) == sizeof(int*)o tamanho da primeira dimensão não é conhecido. O OP não especificou como o array foi obtido.
James McNellis
77

Se arrayfor realmente uma matriz, você pode "zerá-la" com:

memset(array, 0, sizeof array);

Mas há dois pontos que você deve saber:

  • isso funciona apenas se arrayfor realmente um "array two-d", ou seja, foi declarado T array[M][N];para algum tipo T.
  • ele funciona apenas no escopo em que arrayfoi declarado. Se você passá-lo para uma função, o nome array decairá para um ponteiro e sizeofnão fornecerá o tamanho do array.

Vamos fazer um 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;
}

Na minha máquina, as impressões acima:

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

Mesmo sendo arrum array, ele decai para um ponteiro para seu primeiro elemento quando passado para f()e, portanto, os tamanhos impressos f()são "errados". Além disso, f()o tamanho de arr[0]é o tamanho da matriz arr[0], que é uma "matriz [5] de int". Não é o tamanho de um int *, porque o "decaimento" só acontece no primeiro nível, e é por isso que precisamos declarar f()como levando um ponteiro para um array de tamanho correto.

Portanto, como eu disse, o que você estava fazendo originalmente só funcionará se as duas condições acima forem satisfeitas. Caso contrário, você precisará fazer o que outros disseram:

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

Finalmente, memset()e o forloop que você postou não são equivalentes no sentido estrito. Pode haver (e tem havido) compiladores onde "todos os bits zero" não são iguais a zero para certos tipos, como ponteiros e valores de ponto flutuante. Duvido que você precise se preocupar com isso.

Alok Singhal
fonte
memset(array, 0, n*n*sizeof array[0][0]);Eu acho que você quer dizer m*nnão está n*ncerto?
Tagc
Estranhamente, isso não parece funcionar com valores como 1 e 2, em vez de 0.
Ashish Ahuja
memsetfunciona no nível de byte (char). Como 1ou 2não tem os mesmos bytes na representação subjacente, você não pode fazer isso com memset.
Alok Singhal
@AlokSinghal Talvez diga que " intno seu sistema há 4 bytes" em algum lugar antes do exemplo de trabalho mínimo, para que o leitor possa calcular facilmente as somas.
71GA
9

Bem, a maneira mais rápida de fazer isso é não fazer nada.

Parece estranho, eu sei, aqui está um 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;
}

Na verdade, ele ainda está limpando o array, mas apenas quando algo está sendo gravado no array. Esta não é uma grande vantagem aqui. No entanto, se o array 2D foi implementado usando, digamos, uma árvore quádrupla (não dinâmica), ou uma coleção de linhas de dados, então você pode localizar o efeito do sinalizador booleano, mas você precisa de mais sinalizadores. Na árvore quádrupla basta definir o sinalizador vazio para o nó raiz, na matriz de linhas apenas definir o sinalizador para cada linha.

O que leva à pergunta "por que você deseja zerar repetidamente um grande array 2d"? Para que é usado o array? Existe uma maneira de alterar o código para que a matriz não precise ser zerada?

Por exemplo, se você tivesse:

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

ou seja, use-o para um buffer de acumulação, então alterá-lo assim melhoraria o desempenho sem fim:

 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 

Isso não exige que a matriz seja limpa, mas ainda funciona. E isso será muito mais rápido do que limpar a matriz. Como eu disse, a maneira mais rápida é não fazer isso em primeiro lugar.

Skizz
fonte
Maneira alternativa interessante de olhar para o problema.
Beska
1
Não tenho certeza se adicionar uma comparação / ramificação extra para cada leitura vale a pena adiar a inicialização da matriz neste caso (embora possa ser sua). Se o array realmente for tão grande que o tempo de inicialização seja uma preocupação séria, ele poderia usar um hash.
tixxit
8

Se você for realmente obcecado por velocidade (e não tanto por portabilidade), acho que a maneira mais rápida de fazer isso seria usar o vetor intrínseco SIMD. por exemplo, em CPUs Intel, você pode usar estas instruções 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 instrução de armazenamento definirá quatro ints de 32 bits para zero em um acerto.

p deve estar alinhado com 16 bytes, mas essa restrição também é boa para a velocidade porque ajudará o cache. A outra restrição é que p deve apontar para um tamanho de alocação que é um múltiplo de 16 bytes, mas isso também é legal porque nos permite desenrolar o loop facilmente.

Faça um loop e desenrole o loop algumas vezes, e você terá um inicializador muito 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);
}

Há também uma variante _mm_storeuque ignora o cache (ou seja, zerar o array não polui o cache), o que pode fornecer alguns benefícios de desempenho secundários em algumas circunstâncias.

Veja aqui a referência SSE2: http://msdn.microsoft.com/en-us/library/kcwz153a(v=vs.80).aspx

Jarrod Smith
fonte
5

Se você inicializar a matriz com malloc, use calloc; ele irá zerar seu array gratuitamente. (Obviamente, o mesmo desempenho do memset, apenas menos código para você.)

Ben Zotto
fonte
Isso é mais rápido do que o memset se eu quiser zerar repetidamente meu array?
Eddy
calloc irá zerar uma vez, no momento da inicialização, e provavelmente não será mais rápido do que chamar malloc seguido por memset. Depois disso, você fica por conta própria e pode usar o memset se quiser zerar novamente. A menos que seu array seja realmente enorme, o desempenho não é realmente uma consideração aqui em qualquer máquina razoável.
Ben Zotto,
3

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

... pelo menos no GCC 4.8.

Engenheiro
fonte
2

Como seu array 2D foi declarado?

Se for algo como:

int arr[20][30];

Você pode zerá-lo fazendo:

memset(arr, sizeof(int)*20*30);
Pablo Santa Cruz
fonte
Eu usei uma matriz char [10] [10]. Mas recebi o erro: poucos argumentos para funcionar 'memset' e memset(a, 0, sizeof(char)*10*10);funciona bem para mim. , como isso acontece?
noufal
1

Use calloc em vez de malloc. calloc iniciará todos os campos em 0.

int * a = (int *) calloc (n, tamanho de (int));

// todas as células de a foram inicializadas com 0

DUDE_MXP
fonte
0

Acho que a maneira mais rápida de fazer isso manualmente é seguindo o código. Você pode comparar sua velocidade com a função memset, mas não deve ser mais lenta.

(mude o tipo dos ponteiros ptr e ptr1 se o seu tipo de array for diferente do 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
fonte
Seu código provavelmente será mais lento do que memsetpara os tipos de caracteres.
tofro de
0
memset(array, 0, sizeof(int [n][n]));
Swestrup
fonte
1
array [n] [n] é o tamanho de 1 elemento do array, portanto, apenas o primeiro elemento do array seria inicializado.
EvilTeach
Opa. Você está certo. Eu pretendia colocar uma assinatura de tipo nos parênteses, não uma pesquisa de array. Corrigido.
swestrup
0

Você pode tentar isso

int array[20,30] = {{0}};
Călin Calin
fonte
Por favor, adicione mais detalhes
Marko Popovic
-2

Isso acontece porque sizeof (array) fornece o tamanho de alocação do objeto apontado por array . ( array é apenas um ponteiro para a primeira linha de seu array multidimensional). No entanto, você alocou j arrays de tamanho i . Consequentemente, você precisa multiplicar o tamanho de uma linha, que é retornado por sizeof (array) com o número de linhas que você alocou, por exemplo:

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

Observe também que sizeof (array) só funcionará para arrays alocados estaticamente. Para uma matriz alocada dinamicamente, você escreveria

size_t arrayByteSize = sizeof(int) * i * j; 
int *array = malloc(array2dByteSite);
bzero(array, arrayByteSize);
VoidPointer
fonte
A primeira parte está errada. Para sizeofoperador, arraynão é um ponteiro (se foi declarado um array). Veja minha resposta para um exemplo.
Alok Singhal