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

但这仅适用于一维数组。当我 printf 二维数组的内容时，第一行为零，但随后我得到了一堆随机大数字，然后它崩溃了。

Answer 1

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

其中 m 和 n 是二维数组的宽度和高度（在您的示例中，您有一个方形二维数组，因此 m == n)。

Answer 2

如果 array 确实是一个数组，那么您可以使用以下方法将其“归零”：

memset(array, 0, sizeof array);

但是您应该知道两点：

• 只有当 array 确实是“两个-d array”，即为某种类型 T 声明了 T array[M][N];。
• 它仅在声明 array 的范围内有效。如果将其传递给函数，则名称 array 衰减为指针< /a> 和 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] 的大小，这是一个“数组int 的 [5]”。它不是 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;
}

实际上，它仍然在清除数组，但只有当有东西被写入数组时。这在这里并不是一个很大的优势。但是，如果二维数组是使用四叉树（不是动态思维）或数据行集合来实现的，那么您可以本地化布尔标志的效果，但您需要更多标志。在四叉树中，只需为根节点设置空标志，在行数组中，只需为每行设置标志。

这就引出了一个问题“为什么要重复对大型二维数组进行归零”？数组是用来做什么的？有没有办法更改代码以使数组不需要归零？

例如，如果您有：

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 CPU 上，您可以使用这些 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

Answer 5

如果使用 malloc 初始化数组，请改用 calloc；它会免费将您的阵列归零。 （显然与 memset 具有相同的性能，只是代码更少。）

Answer 6

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

...至少在 GCC 4.8 中。

Answer 7

你的二维数组是如何声明的？

如果是这样的：

int arr[20][30];

您可以通过执行以下操作将其归零：

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

Answer 8

使用 calloc 而不是 malloc 。 calloc 会将所有字段初始化为 0。

int *a = (int *)calloc(n,size of(int)) ;

//a的所有单元格都已初始化为0

Answer 9

我认为手动执行此操作的最快方法是遵循代码。您可以将它的速度与 memset 函数进行比较，但它不应该更慢。

（如果您的数组类型与 int 不同，请更改 ptr 和 ptr1 指针的类型）

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

Answer 10

memset(array, 0, sizeof(int [n][n]));

Answer 11

你可以试试这个

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

Answer 12

我没有资格发表评论，但是……

我有点同意 Skizz 的回答，即“最快的方法是[通常]不这样做”，但有一个非常重要的警告。如果您要像这样过滤访问，您确实需要考虑浪费的每个周期。

例如，当 Skizz 有：

void ClearArray ()
{
    array_is_empty = true;
}

int ReadValue (int x, int y)
{
   return array_is_empty ? 0 : array [x][y];
}

我会指出条件 ?: 是一个不必要的分支。要摆脱这个问题，您可以使用值为0或1的整数array_is_empty，然后.. 。

int ReadValue (int x, int y)
{
   return array_is_empty * array [x][y];
}

这会删除条件，但会添加不必要的乘法，编译器不会对其进行优化，因为它不知道 array_is_empty 是否会具有 0 或以外的值 1

因此，我建议使用全 1 的 AND 掩码。这可以是有符号类型中的“-1”表示，也可以是任何简单类型中的~0（零，位翻转）。

int ReadValue (int x, int y)
{
   return array_is_empty & array [x][y];
}

这会产生一个更干净、更快的解决方案，没有不必要的分支预测，也没有缓慢的乘法运算。 AND 的速度非常快，如果您要对数组进行大量查找，则这一点非常重要。

我要添加的最后一个警告要严重得多：

当大多数人将数组归零时，他们期望每个元素都为零。使用“单标志”方法，设置单个元素将删除过滤器并公开所有未初始化的数据......这几乎从来不是用户所期望的。这可能会在以后引起很多头痛。

另一种方法（如 Skizz 所示）是在第一次写入时将数组清零。这消除了该方法的所有潜在好处，只留下缺点和性能损失。

因此，我只会在完全初始化或根本没有初始化的数组上使用它。而且，说实话，这严重限制了它的实用性。

它可以有用的地方是数组在块中使用，例如行......特别是在稀疏占用的情况下。如果每一行或每一块都有这样的标志，那么它就成为一种非常有效的方法。第一次写入时的单个通用“memset”（参见 Skizz 的示例）会消除该方法的任何潜在好处，并且是一个很大的警钟，您应该在构建时将数组归零； ）

另外，还有一点，但是，就我个人而言，我会避免使用“ClearArray”之类的方法名称...我谦虚地认为“MarkUninitialized”或“MarkUnused”可能看起来很难看，但可以避免混淆。

尽管如此，这一切都归功于斯基兹的回答。当有意义的事情去做时，它就非常值得去做。避免不必要的工作与稍后优化重构一样好； ）

我很抱歉回答这个问题。我只是认为值得指出，考虑到数组访问期间的额外工作有多快失控......以及 memset-on-first-write 的问题

Answer 13

发生这种情况是因为 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);