C에서 2D 어레이를 0으로 설정하는 가장 빠른 방법?

C에서 2D 어레이를 0으로 설정하는 가장 빠른 방법?

나는 C에 큰 2D 배열을 반복해서 0으로 만들고 싶다.지금 내가 하는 일은 다음과 같다.

// 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(array, 0, sizeof(array))

그러나 이는 1D 어레이에만 해당된다.2D 배열의 내용을 인쇄할 때 첫 번째 행은 0이 되는데, 그때 임의의 큰 숫자의 로드가 와서 충돌한다.

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

어디에m그리고n 때문에 2차원 배열(의차원: 2차원 배열)m == n).

만약array진정한 어레이인 경우, 다음을 통해 "제로아웃"할 수 있다.

memset(array, 0, sizeof array);

그러나 알아야 할 두 가지 점이 있다.

• 이것은 오직 다음과 같은 경우에만 효과가 있다.array정말 "2D 배열"이다, 다시 말해, 선언되었다.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". 그것은 a의 크기가 아니다.int *왜냐하면 "파괴"는 오직 1단계에서만 일어나기 때문에, 우리가 선언할 필요가 있는 것이다.f()올바른 크기의 배열로 포인터를 가져가는 것.

그래서, 내가 말했듯이, 네가 원래 하던 일은 위의 두 조건이 충족되어야만 효과가 있을 거야.그렇지 않다면 다른 사람이 말한 대로 해야 할 것이다.

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

마지막으로memset()그리고for당신이 게시한 루프는 엄밀한 의미에서 동등하지 않다.포인터와 부동 소수점 값과 같은 특정 유형에 대해 "모든 비트 0"이 0이 아닌 컴파일러가 있을 수 있다(그리고 존재했다).하지만 네가 그것에 대해 걱정할 필요는 없을 것 같아.

글쎄, 가장 빠른 방법은 아예 하지 않는 거야.

이상하게 들리는데, 여기 몇 가지 가성이 있어.

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 배열이 예를 들어 동적 한 마음이 아닌 쿼드 트리 또는 데이터 열을 사용하여 구현된 경우 부울 깃발의 효과를 로컬로 확인할 수 있지만 플래그가 더 많이 필요할 수 있다.쿼드 트리에서 루트 노드의 빈 플래그를 설정하고 행 배열에서 각 행의 플래그를 설정하십시오.

"대규모 2D 어레이를 반복적으로 0으로 설정하려는 이유"라는 질문으로 이어지는 것은?이 배열은 무엇에 사용되는가?어레이에 영점 조정이 필요하지 않도록 코드를 변경하는 방법이 있는가?

예를 들어 다음과 같은 경우:

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 

이것은 배열을 지울 필요가 없지만 여전히 작동한다.그리고 그것은 배열을 지우는 것보다 훨씬 빠를 것이다.내가 말했듯이, 가장 빠른 방법은 애당초 하지 않는 것이다.

로 배열을 초기화하는 경우malloc, 사용calloc대신, 그것은 무료로 당신의 배열을 제로화할 것이다. (동일하게 memset과 같은 perfence, 단지 당신을 위한 코드만 적을 뿐이다.)

malloc 대신 calloc를 사용하십시오. calloc는 모든 필드를 0으로 시작한다.

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

//의 모든 셀이 0으로 초기화됨

만약 여러분이 정말로, 정말로 속도에 사로잡혀 있다면(그리고 이식성에는 별로 집착하지 않는다) 이렇게 하는 가장 빠른 방법은 SIMD 벡터 본질(예: Intel CPU에서)을 사용하는 것이라고 생각한다.

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

각 매장 지침은 한 번의 히트곡에 4개의 32비트 인트를 0으로 설정한다.

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캐시를 바이패스하는 기능(즉, 어레이를 0으로 설정해도 캐시가 오염되지 않음)으로, 어떤 상황에서는 2차 성능 이점을 얻을 수 있다.

SSE2 참조는 여기를 참조하십시오. http://msdn.microsoft.com/en-us/library/kcwz153a(v=vs.80).aspx

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

적어도 GCC 4.8에서는 말이야

2D 어레이를 어떻게 선언하셨습니까?

다음과 같은 경우:

int arr[20][30];

다음을 수행하여 0으로 설정할 수 있다.

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

손으로 하는 가장 빠른 방법은 코드를 따르는 것이라고 생각한다.속도를 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;
}

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

이거 먹어봐.

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

평판은 없지만...

나는 "가장 빠른 방법은 하지 않는 것이다"라는 스키즈의 대답에 다소 동의하지만, 매우 중요한 주의사항을 담고 있다.이렇게 액세스를 필터링하려면 모든 사이클이 낭비되는 것을 고려해야 한다.

예를 들어, Skizz가 가지고 있는 위치:

void ClearArray ()
{
    array_is_empty = true;
}

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

나는 조건부 ?:는 불필요한 가지라고 지적하고 싶다.이 문제를 제거하려면 0 또는 1의 정수 배열_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는 매우 빠르며, 이 필터링을 배열에서 많은 수의 룩업을 통해 수행할 경우 매우 중요할 것이다.

내가 덧붙이고 싶은 마지막 경고는 훨씬 더 심각하다.

대부분의 사람들이 배열을 0으로 설정할 때, 그들은 각 원소가 0이 될 것으로 예상한다.'단일 플래그' 접근 방식으로 단일 요소를 설정하면 필터를 제거하고 초기화되지 않은 모든 데이터가 노출되며...사용자가 예상하는 것은 거의 없다.이것은 나중에 많은 두통을 일으킬 수 있다.

(Skizz가 보여주듯이) 대안은 첫 번째 쓰기에서 배열을 0으로 설정하는 것이다.이는 접근방식의 모든 잠재적 이점을 무효화하고 성능 저하와 손실만 남긴다.

그래서, 나는 이것을 완전히 초기화되거나 전혀 초기화되지 않은 배열에만 사용할 것이다.그리고 솔직히 말해서, 그것은 그것의 유용성을 심각하게 제한한다.

그것이 유용하게 사용될 수 있는 곳은 특히 드물게 점유되었을 때 선과 같은 블록에서 어레이가 사용되는 곳이다.각 선이나 블록에 그러한 깃발이 있다면 그것은 매우 효율적인 접근법이 된다.첫 번째 쓰기(Skizz의 예시 참조)에서 하나의 일반 'memset'은 접근 방식의 잠재적인 이점을 해제하며, 단지 시공 시 어레이를 0으로 설정하라는 큰 경보 벨이다; )

사소한 문제지만, 개인적으로 "ClearArray" 같은 메서드 이름은 피하고 싶은데...나는 "MarkUnitialized" 또는 "MarkUnused"가 추해 보일 수 있지만 혼란을 피할 수 있다는 점을 겸허히 제출한다.

그럼에도 불구하고, 모든 것은 스키즈의 대답에 대한 공로를 인정한다.하는 것이 이치에 맞으면, 충분히 할 가치가 있다.피한 불필요한 작업은 나중에 최적화하는 리팩터만큼 좋다; )

이렇게 대답해줘서 미안해.어레이 액세스 중 추가 작업이 얼마나 빨리 통제 불능이 되는지를 고려할 때, 지적할 가치가 있다고 생각했을 뿐인데...첫 글에 memset-on-first-write와 관련된 문제

이는 sizeof(array)가 어레이별로 가리킨 개체의 할당 크기를 제공하기 때문에 발생한다.(어레이는 다차원 배열의 첫 번째 행에 대한 포인터일 뿐이다.)그러나 당신은 j 배열을 크기 i로 할당했다.따라서 한 행의 크기를 (배열)의 크기에 할당하는 행 수와 곱해야 한다.

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

또한 크기(어레이)는 정적으로 할당된 어레이에만 사용할 수 있다는 점에 유의하십시오.동적으로 할당된 어레이의 경우 기록할 대상

size_t arrayByteSize = sizeof(int) * i * j; 
int *array = malloc(array2dByteSite);
bzero(array, arrayByteSize);

참조URL: https://stackoverflow.com/questions/2516096/fastest-way-to-zero-out-a-2d-array-in-c