2차원 어레이 대 1차원 어레이의 성능

2차원 어레이 대 1차원 어레이의 성능

C에서, m×n 2차원 배열과 길이 m×n의 1차원 배열 사이에 시간과 공간의 차이가 있습니까? (m과 n의 큰 값의 경우)1차원 배열로 요소에 액세스하는 것이 더 빠를까요?

C에서 2차원 배열은 1차원 배열을 위한 깔끔한 색인 체계일 뿐입니다.메모리의 하고, 1D 어레이는 2D 어레이와 마찬가지로,A[row][col]표기법은 말하는 것과 비슷합니다.A[row*NCOLS+col].

일반적으로 단일 차원 배열을 사용하여 자체 다차원 배열을 구현하는 경우 인덱싱 기능을 작성합니다.

int getIndex(int row, int col) { return row*NCOLS+col; }

컴파일러가 이 함수를 인라인화한다고 가정하면, 여기서의 성능은 2D 어레이의 내장된 '인덱스 기능'을 사용한 것과 정확히 같습니다.

설명하기:

#define NROWS 10
#define NCOLS 20

다음 항목:

int main(int argc, char *argv[]) {
    int myArr[NROWS*NCOLS];
    for (int i=0; i<NROWS; ++i) {
       for (int j=0; j<NCOLS; ++j) {
          myArr[getIndex(i,j)] = i+j;
       }
    }
    return 0;
}

다음과 같은 작업을 수행해야 합니다.

int main(int argc, char *argv[]) {
    int myArr[NROWS][NCOLS];
    for (int i=0; i<NROWS; ++i) {
       for (int j=0; j<NCOLS; ++j) {
          myArr[i][j] = i+j;
       }
    }
    return 0;
}

아라케이님이 지적하신 것처럼 행을 많이 뛰어다니고 행이 매우 크면 페이지 폴트가 많이 발생할 수 있습니다...이 경우 사용자 지정 인덱싱 기능(행과 콜이 전환됨)이 도움이 될 수 있지만, 2차원 배열에서 행으로 처리하는 차원과 열로 처리하는 차원을 간단히 변경할 수 있습니다.

실제로 C에서 소위 2차원 배열을 사용하면 컴파일러가 1차원 배열로 매핑을 해줍니다.1차원 배열을 사용하고 2차원 배열로 취급하려면 매핑을 직접 작성해야 합니다.

당신이 유일하게 주의해야 할 것은 당신이 배열에 행 단위로 접근하는 것입니다. 왜냐하면 C 컴파일러는 당신의 2차원 배열 행을 행 단위로 저장할 것이기 때문입니다.'큰' 2차원 배열을 열 단위로 액세스하면 페이지 결함이 발생할 가능성이 높습니다.1차원 배열만 지원하는 언어로 프로그래밍하는 경우에도 매핑을 여러 차원으로 쉽게 작성할 수 있습니다.

행 단위로 매핑을 수행하려면 이 위키백과 기사를 보십시오.매핑은 FORTRAN 행렬과 같이 열 단위로 할 수 있습니다.

로버트 말이 맞습니다.색인식은 포인터 산술식으로 컴파일되므로 차이가 없습니다.

그러나 영향을 미칠 수 있는 것은 액세스 순서이므로, 액세스 순서를 제어할 수 있도록 사용자가 직접 구현하기를 원할 수 있습니다.예를 들어 열 첫 번째 대 행 첫 번째 형식입니다.

최신 프로세서에서 다양한 단계에서 대규모 어레이에 액세스하면 예상치 못한 성능 차이가 발생할 수 있습니다.순차 액세스가 항상 가장 빠르며, 캐시 상호 작용으로 인해 다른 단계에서는 최대 30배까지 느려질 수 있습니다.내부 차원이 2의 거듭제곱인 다차원 어레이는 캐시 연관성과 상호 작용하는 방식 때문에 성능이 떨어지는 경우가 많습니다.이러한 문제를 이해하기 위해서는 측정을 대신할 수 없습니다.

저는 차이가 없다고 생각합니다.내부적으로 c는 2차원 배열을 순차적으로 여러 개의 1차원 배열처럼 처리합니다.

그러나 모든 성능과 마찬가지로 마일리지가 다를 수 있습니다.약간의 미묘한 포인터 산술적 차이가 있을 수 있습니다.두 시나리오 모두에서 시간 제한 테스트를 실행합니다.빨리 달리는 쪽이 승리합니다.

다른 사람들이 말했듯이, 정말로 다른 점은 항목에 액세스하는 방법입니다. 적어도 공통 아키텍처에서 항목이 선형적으로 메모리에 배치되는 방식이 중요하다는 것입니다.그래서 당신이 가지고 있는 것은 1d 어레이, 2d 등뿐입니다.는 "그냥" 편리한 것이며, 합리적인 컴파일러는 인덱싱을 최적화해야 합니다. 그러나 실제로는 변수가 몇 개 이상 있으면 레지스터 부족으로 인해 컴파일러가 x86과 같은 arch에서 실패하는 경우가 많습니다.

이제는 애플리케이션에 따라 다르지만, 특히 다중 차원을 처리해야 할 경우 기본적으로 1d 레이아웃으로 생각해야 한다고 생각합니다.C에서 다차원 배열의 첫 번째 문제는 동적으로 할당할 수 없다는 것입니다. 행 단위로 할당하면 연속적인 메모리 조각이 없기 때문에 성능이 저하됩니다.자세한 내용은 FFTW 설명서를 참조하십시오.

편리한 배열 인덱싱을 통해 단일 메모리를 항상 설명할 수 있습니다(큰 nxm 메모리 블록 하나를 할당한 다음 각 행에 n 포인터 배열을 만듭니다).

저는 추측할 뿐이지만, 1d 배열이 2d 배열보다 빠르다고 생각합니다.하지만, 그것은 측정적으로 더 빠르지는 않을 것입니다.약 $1,000,000.01은 $1,000,000 이상입니다.

코드화하기 쉬운 것을 사용하겠습니다.

언급URL : https://stackoverflow.com/questions/1242705/performance-of-2-dimensional-array-vs-1-dimensional-array