다차원 배열을 만드는 가장 좋은 방법은 무엇입니까?

Question

STL 컨테이너와 관련하여 정말 기본적인 질문이 있습니다. 내 요구 사항은 내가 다차원 배열의 형태로 double 값을 저장하고자한다는 것입니다. I는 I는 [] 연산자를 이용하여 루프에 사용 & itterating하고 이것을 즉

myvector[4] = myvector[3] - 2 * myvector[2]; 

직접 대수에 다양한 동작을 수행한다. 나는 STL itterator를 사용하지 않는다. 나는 두 가지 기본 접근법을 발견했다. here. 저는 메모리 효율보다 속도가 더 좋습니다. 이러한 변수에 자주 액세스하고 있기 때문에 벡터가 저에게 느릴 것이라고 생각합니다. 이 문제에 대한 겸손한 의견은 무엇입니까? 그 대답은 이전 경험을 바탕으로 이루어질 것이라는 것을 알고 있습니다. 그래서 나는이 질문을하고 있습니다. 이 질문이 여기에서 논의하기에는 너무 근본적이라면 미안합니다.

Answer 1

제공된 링크는 "실제"2 차원 어레이를 만드는 2 가지 방법을 나열했습니다. 일반적으로 2 차원 어레이는 많은 할당이 필요하기 때문에 효율적이지 않습니다. 여기

// Array of length L and width W 
type* array1 = new type[L * W]; // raw pointers 
std::vector<type> array2(L * W); // STL Vector 

// Accessing a value. You have to use a convention for indices, and follow it. 
// Here the convention is: lines are contiguous (index = x + y * W) 
type value = array[x + y * W]; // raw pointer array & vector 

가 (당신이 타이머 부분을 변경하는 경우를 제외하고, 단지 창) 간단한 벤치 마크 : 대신, 당신은 가짜 2 차원 배열을 사용하여 컴파일 된

#include <vector> 
#include <ctime> 
#include <iostream> 
#include <stdlib.h> 

#include <Windows.h> 
typedef LARGE_INTEGER clock_int; 

void start_timer(clock_int& v) 
{ 
    QueryPerformanceCounter(&v); 
} 

void end_timer(clock_int v, const char* str) 
{ 
    clock_int e; 
    QueryPerformanceCounter(&e); 
    clock_int freq; 
    QueryPerformanceFrequency(&freq); 
    std::cout << str << 1000.0 * ((double)(e.QuadPart-v.QuadPart)/freq.QuadPart) << " ms\n"; 
} 

void test_2d_vector(unsigned int w, unsigned int h) 
{ 
    std::vector<std::vector<double> > a; 
    a.resize(h); 
    for(unsigned int t = 0; t < h; t++) 
     a[t].resize(w); 

    clock_int clock; 
    start_timer(clock); 
    // Benchmark random write access 
    for(unsigned int t = 0; t < w * h; t++) 
     a[rand() % h][rand() % w] = 0.0f; 
    end_timer(clock,"[2D] Random write (STL) : "); 

    start_timer(clock); 
    // Benchmark contiguous write access 
    for(unsigned int y = 0; y < h; y++) 
     for(unsigned int x = 0; x < w; x++) 
      a[y][x] = 0.0f; 
    end_timer(clock,"[2D] Contiguous write (STL) : "); 
} 

void test_2d_raw(unsigned int w, unsigned int h) 
{ 
    double** a = new double*[h]; 
    for(unsigned int t = 0; t < h; t++) 
     a[t] = new double[w]; 

    clock_int clock; 
    start_timer(clock); 
    // Benchmark random write access 
    for(unsigned int t = 0; t < w * h; t++) 
     a[rand() % h][rand() % w] = 0.0f; 
    end_timer(clock,"[2D] Random write (RAW) : "); 

    start_timer(clock); 
    // Benchmark contiguous write access 
    for(unsigned int y = 0; y < h; y++) 
     for(unsigned int x = 0; x < w; x++) 
      a[y][x] = 0.0f; 
    end_timer(clock,"[2D] Contiguous write (RAW) : "); 
} 

void test_1d_raw(unsigned int w, unsigned int h) 
{ 
    double* a = new double[h * w]; 

    clock_int clock; 
    start_timer(clock); 
    // Benchmark random write access 
    for(unsigned int t = 0; t < w * h; t++) 
     a[(rand() % h) * w + (rand() % w)] = 0.0f; 
    end_timer(clock,"[1D] Random write (RAW) : "); 

    start_timer(clock); 
    // Benchmark contiguous write access 
    for(unsigned int y = 0; y < h; y++) 
     for(unsigned int x = 0; x < w; x++) 
      a[x + y * w] = 0.0f; 
    end_timer(clock,"[1D] Contiguous write (RAW) : "); 
} 

void test_1d_vector(unsigned int w, unsigned int h) 
{ 
    std::vector<double> a(h * w); 

    clock_int clock; 
    start_timer(clock); 
    // Benchmark random write access 
    for(unsigned int t = 0; t < w * h; t++) 
     a[(rand() % h) * w + (rand() % w)] = 0.0f; 
    end_timer(clock,"[1D] Random write (STL) : "); 

    start_timer(clock); 
    // Benchmark contiguous write access 
    for(unsigned int y = 0; y < h; y++) 
     for(unsigned int x = 0; x < w; x++) 
      a[x + y * w] = 0.0f; 
    end_timer(clock,"[1D] Contiguous write (STL) : "); 
} 

int main() 
{ 
    int w=1000,h=1000; 
    test_2d_vector(w,h); 
    test_2d_raw(w,h); 
    test_1d_vector(w,h); 
    test_1d_raw(w,h); 
    system("pause"); 
    return 0; 
} 

을 msvc2010, 릴리스/황소/

[2D] Random write (STL) : 32.3436 ms 
[2D] Contiguous write (STL) : 0.480035 ms 
[2D] Random write (RAW) : 32.3477 ms 
[2D] Contiguous write (RAW) : 0.688771 ms 
[1D] Random write (STL) : 32.1296 ms 
[1D] Contiguous write (STL) : 0.23534 ms 
[1D] Random write (RAW) : 32.883 ms 
[1D] Contiguous write (RAW) : 0.220138 ms 

당신은 STL 원시 포인터에 해당 볼 수 있습니다 : 구약, 나를 위해 (Win7에 x64의 인텔 코어 i7 2600K)를 출력합니다. 그러나 1D는 2D보다 훨씬 빠릅니다.