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

92

Я хочу несколько раз обнулить большой 2-мерный массив в 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-массива, первая строка нули, но затем я получил загрузку случайных больших чисел, и она вылетела.

Эдди
источник

Ответы:

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

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

Джеймс МакНеллис
источник
1
Похоже, это не работает. Я получаю «процесс вернулся -1073741819» на кодовых блоках, что является ошибкой сегмента, верно?
Эдди,
8
@Eddy: Покажите нам объявление массива.
GManNickG
1
Бьюсь об заклад, он вылетает на других строках, а не на memset, потому что вы упомянули сбой из-за обнуления только одной строки.
Blindy
3
Ага. Просто попробовал протестировать массив, объявленный как int d0=10, d1=20; int arr[d0][d1], и memset(arr, 0, sizeof arr);работал, как ожидалось (gcc 3.4.6, скомпилирован с -std=c99 -Wallфлагами). Я понимаю, что «это работает на моей машине» означает неумелое приседание, но это memset(arr, 0, sizeof arr); должно было сработать . sizeof arr должен возвращать количество байтов, используемых всем массивом (d0 * d1 * sizeof (int)). sizeof array[0] * m * nне даст вам правильный размер массива.
Джон Боде,
4
@John Bode: Верно, но это зависит от того, как получается массив. Если у вас есть функция, которая принимает параметр int array[][10], то sizeof(array) == sizeof(int*)размер первого измерения неизвестен. OP не уточнил, как был получен массив.
Джеймс МакНеллис
79

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

Алок Сингхал
источник
memset(array, 0, n*n*sizeof array[0][0]);Я думаю, вы имеете в виду m*nне так n*n?
Tagc
Как ни странно, похоже, что это не работает со значениями типа 1 и 2 вместо 0.
Ашиш Ахуджа
memsetработает на уровне байтов (символов). Поскольку в базовом представлении есть 1или 2нет одинаковых байтов, вы не можете этого сделать с помощью memset.
Алок Сингхал
@AlokSinghal Может быть, укажите, что « intв вашей системе 4 байта» где-то перед минимальным рабочим примером, чтобы читатель мог легко вычислить суммы.
71GA,
9

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

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

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 

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

Skizz
источник
Интересный альтернативный способ взглянуть на проблему.
Beska
1
Я не уверен, что добавление дополнительного сравнения / ветки для каждого отдельного чтения стоит отложить инициализацию массива в этом случае (хотя может быть вашим). Если массив действительно настолько велик, что время инициализации вызывает серьезную озабоченность, тогда он может использовать вместо него хеш.
tixxit
8

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

Джаррод Смит
источник
5

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

Бен Зотто
источник
Это быстрее, чем memset, если я хочу многократно обнулять свой массив?
Эдди,
calloc обнулит его один раз, во время инициализации, и, вероятно, не будет быстрее, чем вызов malloc с последующим memset. После этого вы сами по себе и можете просто использовать memset, если хотите снова обнулить его. Если ваш массив действительно огромен, производительность здесь не рассматривается ни на одной разумной машине.
Бен Зотто
3

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

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

Инженер
источник
2

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

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

int arr[20][30];

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

memset(arr, sizeof(int)*20*30);
Пабло Санта Крус
источник
Я использовал массив char [10] [10]. Но я получил ошибку: слишком мало аргументов для функции memset, и memset(a, 0, sizeof(char)*10*10);у меня все работает. , как это происходит?
noufal
1

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

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

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

DUDE_MXP
источник
0

Я думаю, что самый быстрый способ сделать это вручную - это выполнить код. Вы можете сравнить его скорость с функцией 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]);

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

mack369
источник
Ваш код, скорее всего, будет медленнее, чем memsetдля типов char.
tofro
0
memset(array, 0, sizeof(int [n][n]));
swestrup
источник
1
array [n] [n] - это размер 1 элемента массива, поэтому будет инициализирован только первый элемент массива.
EvilTeach
Ой. Вы правы. Я хотел поместить в скобки подпись типа, а не поиск по массиву. Починил это.
swestrup
0

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

int array[20,30] = {{0}};
Кэлин Калин
источник
Пожалуйста, добавьте подробности
Марко Попович
-2

Это происходит потому, что sizeof (array) дает вам размер выделения объекта, на который указывает array . ( массив - это просто указатель на первую строку вашего многомерного массива). Однако вы выделили j массивов размера i . Следовательно, вам нужно умножить размер одной строки, которую возвращает sizeof (array), на количество выделенных вами строк, например:

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

Также обратите внимание, что sizeof (array) будет работать только для статически распределенных массивов. Для динамически распределенного массива вы должны написать

size_t arrayByteSize = sizeof(int) * i * j; 
int *array = malloc(array2dByteSite);
bzero(array, arrayByteSize);
VoidPointer
источник
Первая часть неверна. sizeofОператор For arrayне является указателем (если он был объявлен как массив). См. Мой ответ для примера.
Алок Сингхал,