Самый быстрый способ обнулить 2d массив в C?

Question

Я хочу многократно обнулить большой двумерный массив в C. Это то, что я делаю в данный момент:

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

Я пытался использовать memset:

memset(array, 0, sizeof(array))

Но это работает только для одномерных массивов. Когда я печатаю содержимое 2D-массива, первая строка равна нулю, но затем я получаю массу случайных больших чисел, и она вылетает.

Answer 1

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

Где m и n - ширина и высота двумерного массива (в вашем примере у вас есть квадратный двумерный массив, поэтому m == n).

Answer 2

Если array действительно массив, то вы можете обнулить его с помощью:

memset(array, 0, sizeof array);

Но есть два момента, которые вы должны знать:

• это работает, только если array действительно является "двумерным массивом", т.е. было объявлено T array[M][N]; для некоторого типа T.
• работает только в области, где было объявлено array. Если вы передадите его в функцию, то имя array распадется на указатель , и sizeof не даст вам размер массива.

Давайте проведем эксперимент:

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

На моей машине выше напечатано:

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

Несмотря на то, что arr является массивом, при передаче в f() он распадается на указатель на свой первый элемент, и поэтому размеры, напечатанные в f(), являются «неправильными». Кроме того, в f() размер arr[0] равен размеру массива arr[0], который представляет собой «массив [5] из int». Это не размер int *, потому что «распад» происходит только на первом уровне, и поэтому мы должны объявить f() как указатель на массив правильного размера.

Итак, как я уже сказал, то, что вы делали изначально, будет работать, только если выполнены два вышеуказанных условия. Если нет, вам нужно будет сделать то, что сказали другие:

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

Наконец, memset() и опубликованный вами цикл for не являются в строгом смысле эквивалентными. Могут быть (и были) компиляторы, в которых «все биты ноль» не равны нулю для определенных типов, таких как указатели и значения с плавающей точкой. Я сомневаюсь, что вам нужно об этом беспокоиться.

Answer 3

Ну, самый быстрый способ сделать это - вообще не делать этого.

Звучит странно, я знаю, вот какой-то псевдокод:

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

На самом деле, он все еще очищает массив, но только когда что-то записывается в массив. Это не большое преимущество здесь. Однако, если двумерный массив был реализован с использованием, скажем, четырехугольного дерева (а не динамического разума) или набора строк данных, то вы можете локализовать эффект логического флага, но вам потребуется больше флагов. В четырехугольном дереве просто установите пустой флаг для корневого узла, в массиве строк просто установите флаг для каждой строки.

Что приводит к вопросу "почему вы хотите повторно обнулять большой 2d массив"? Для чего используется массив? Есть ли способ изменить код, чтобы массив не нуждался в обнулении?

Например, если у вас было:

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

то есть, используйте его для буфера накопления, а затем измените его так, что это улучшит производительность без конца:

 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 

Это не требует очистки массива, но все еще работает. И это будет намного быстрее, чем очистка массива. Как я уже сказал, самый быстрый способ - это не делать это в первую очередь.

Answer 4

Если вы действительно, действительно одержимы скоростью (и не настолько мобильностью), я думаю, что абсолютный самый быстрый способ сделать это - использовать SIMD-векторную характеристику.Например, на процессорах Intel вы можете использовать следующие инструкции 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.

Каждая инструкция сохранения будет устанавливать четыре 32-битных целых числа в ноль за один удар., но это ограничение также хорошо для скорости, потому что это поможет кешу.Другое ограничение состоит в том, что p должен указывать на размер выделения, кратный 16-байтам, но это тоже здорово, поскольку он позволяет нам легко развернуть цикл.

Имейте это в цикле и развернитецикл несколько раз, и у вас будет сумасшедший быстрый инициализатор:

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

Существует также вариант _mm_storeu, который обходит кеш (т. е. обнуление массива не будет загрязнять кеш), котороеможет дать вам некоторые дополнительные преимущества производительности в некоторых обстоятельствах.

См. Здесь для ссылки SSE2: http://msdn.microsoft.com/en-us/library/kcwz153a(v=vs.80).aspx

Answer 5

Если вы инициализируете массив с malloc, используйте calloc; он обнулит ваш массив бесплатно. (То же самое, что и memset, только меньше кода для вас.)

Answer 6

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

... по крайней мере, в GCC 4.8.

Answer 7

Как был объявлен ваш 2D массив?

Если это что-то вроде:

int arr[20][30];

Вы можете обнулить его, выполнив:

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

Answer 8

Используйте calloc вместо malloc. calloc инициирует все поля в 0.

int * a = (int *) calloc (n, размер (int));

// все ячейки были инициализированы в 0

Answer 9

Вы можете попробовать это

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

Answer 10

Я думаю, что самый быстрый способ сделать это вручную - это следовать коду. Вы можете сравнить его скорость с функцией memset, но она не должна быть медленнее.

(изменить тип указателей ptr и ptr1, если ваш тип массива отличается от 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]);

<pre> while(ptr < ptr1) { *ptr++ = 0; }