1

私は STL コンテナに関して非常に基本的な疑問を持っています。私の要件は、多次元配列の形式で double 値を格納することです。それらに対してさまざまな代数演算を直接実行します。

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

このため、 for ループと [] 演算子を使用して繰り返しています。私は STL itterator を使用していません。ここで 2 つの基本的なアプローチを見つけました。私はメモリ効率よりも速度を好みます。私はこれらの変数に頻繁にアクセスしているので、ベクターは遅いと思います。では、この問題についてあなたの謙虚な意見は何ですか? 答えがあなたの以前の経験に基づいていることはわかっています。そのため、この質問をしています。この質問が基本的すぎてここで議論できない場合は申し訳ありません。

4

1 に答える 1

4

あなたが与えたリンクには、「実際の」2次元配列を作成する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

これは簡単なベンチマークです（タイマー部分を変更した場合を除いて、Windowsのみ）：

#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 でコンパイルし、/Ox /Ot をリリースすると、出力されます (Win7 x64、Intel Core i7 2600K):

[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 が raw ポインターと同等であることがわかります。しかし、1D は 2D よりもはるかに高速です。

于 2012-11-04T13:31:10.753 に答える