vector memory allocate

宣告:

STL vector<vector<struct>>

memory allocate:

method 1: dynamically allocated.

method 2: 直接宣告n*n block, 每個1*1 block 為struct.

當然第二種方式較優, 進行新增刪除效率都較佳.

Q1. 請問vector<vector<struct>>是用哪種方法分配空間

Q2. 如果要用, method 2去宣告該如何做

ps. 因為我要進行影像處理, 其陣列約為4096*4096, 所以method 1(2) 其效率會差蠻大.

Update:

了解, 謝謝.

ex1.

struct Pixel[n][n];

請問這樣宣告還會去dynamical allocated?

ex2.

coordinate include x-axis and y-axis

vector v1; == vector v2;

v2大小為v1兩倍. (因為v1每個1*1 pixel 包含兩個int)

vector 也會進行dynamical allocated,

若利用addr(x, y)=bmpWidth*y + x,

計算x, y位於1D array的位址

Update 2:

這樣是否分配(刪除)空間, 較有效率(迅速)?

Update 3:

如果ex1 也是採用dyanmical allocate,

int image[n][n][3];

若要不使用dynamical allocated,

這樣不就要宣告成int image[n*n*3],

並且要建立addressOperation(), 個別計算image[i][i][0] 、image[i][i][1] 、image[i][i][2] 位址.

Update 4:

To Tai:

Q1 if your structure is struct A { };

vector < vector < A > > img( n, vector < A > (n));

一般而言我能使用reserve就使用reserve(push_back()新增資料), 因為上方的initialization,

及resize(), 會進行初始化, 除非我有需要直接assign位址.

Update 5:

在V.S. 2012 struct Pixel[n][n]; 無法直接這樣宣告, 必須使用dynamical allocated

Update 6:

感謝以上網友的意見,

有以下幾個問題:

Q1.

vector.reserve(n)在vector內, 代表我配置n個空間, 但是不給予初始化,

利用push_back(), 就可把資料寫入(因為reserve過, 所以不會有memory copy)

請問我的觀念有錯誤?

倘若非如此, 那reserve的意義是什麼?

Update 7:

Q2.

因為malloc 的n值並非固定, 無法直接宣告image[const][const],

若不用 1D array 模擬 2D array,addressOperation() 對 2D image filtering 等等處理,

我應該怎麼做?

Update 8:

每個image[i][i]內的大小為struct, 這樣不就一定要triple pointer去分配空間?

"1D array 模擬 2D array" (single pointer) 其實就是不希望allocate耗費太多時間,

利用轉址函數, 去找實際位址, 這樣的成本會比triple pointer allocate還高?

Update 9:

ps. 讀入影像為4096*4096

並且會有其他演算法, 將4096*4096 copy到其他陣列, 進行一些運算, 取得其他結果!

Update 10:

也可能為2048*2048 這是變動的

Update 11:

Q3.

vector< vector < Pixel > > img (height, vector < Pixel > (width) );

他初始化都是pixel.x=0 pixel.y=0, 要怎麼讓初始化為255, 還是說沒辦法只能另外assign,

img[i][j]=255?

4 Answers

Rating
  • Tai
    Lv 5
    7 years ago
    Favorite Answer

    Q2 if your structure is struct A { };

    vector < vector < A > > img( n, vector < A > (n));

    2013-11-30 14:36:45 補充:

    Sorry 我寫錯了。我回答的是 method 1 怎麼用 vector< vector < your_struct > > 配置。

    2013-11-30 16:09:06 補充:

    而 vector < vector < A > > img( n, vector < A > (n));

    內部記憶體其實跟下面類似

    A **img = new *A[n];

    for (int i = 0; i < n; ++i) A[i] = new A[n];

    而 A** 建構的動態陣列結構,跟下面的結構是一樣的

    #define n 4096

    A img[n][n];

    存取成本 (index 計算) 也相同。所以最佳化時,使用 vector< vector > > 的存取速應該是跟二維陣列一樣。

    2013-11-30 16:43:45 補充:

    A **img = new *A[n];

    for (int i = 0; i < n; ++i) A[i] = new A[n]; => 筆誤

    for (int i = 0; i < n; ++i) img[i] = new A[n];

    如果你要 "自己作" 最適合影像處理的 dynamic 2D, 應該是上式。

    用 1D array 模擬 2D array,addressOperation() 對 2D image filtering 等等處理,是很多餘的計算,每個位址都要一個乘法一個加法。

    2013-11-30 17:08:32 補充:

    // 1D simulate 2D

    Pixel *img = new Pixel[n];

    或用

    vector < Pixel > img = vector (n);

    // 2D array

    Pixel **img = new *Pixel[height];

    for (int i = 0; i < height; ++i) img[i] = new Pixel[width];

    或用

    vector< vector < Pixel > > img (height, vector < Pixel > (width) );

    2013-11-30 19:50:21 補充:

    其實有疑點需釐清,也許版大先 reserve 再 push_back 是好方法。不過意見額度沒了,先貼在回答區。

    ctr : constructor 簡寫

    cpy: copy 簡寫

    總之有效率之初始化整張圖, 要看 ctr, cpy, loop 成本

    (1) vector<vector<Pixel>> img(n, vector<Pixel>(n));

    一般/最佳化: n ctr + (n+nxn) cpy + 0-loop

    (nxn cpy 是由內部 n 次 vector<Pixel>(n) 的 vector copy 造成)

    但最佳化中,n 次 vector copy 會被加速。

    (2) reserve, push_back

    一般/最佳化: reserve + 0 ctr + nxn cpy + nxn-loop

    (ctr+cpy) 的數量較少, 但需要 nxn for-loop overhead。

    既然 (1)(2) 有 copy 成本,乾脆都用 constructor

    (3) Pixel** img.

    一般/最佳化:: n*n ctr + 0 cpy + n-loop

    只有 n 次 for-loop, 整體最快

    #include <iostream>

    #include <time.h>

    #include <vector>

    using namespace std;

    static long long ctr=0;

    static long long cpy=0;

    struct Pixel {

    int c[3];

    Pixel(){

    c[0]=c[1]=c[2]=0;

    ctr++;

    }

    Pixel(const Pixel& p) {

    *this = p;

    cpy++;

    }

    };

    int main()

    {

    int n = 4096;

    Pixel c;

    clock_t t;

    for (int i = 0; i < 10; ++i)

    {

    ctr = cpy = 0;

    t = clock();

    vector<vector<Pixel>> img1(n, vector<Pixel>(n));

    cout << "img1 " << clock()-t << "\n";

    cout << "ctr=" << ctr << " cpy=" << cpy << " loop=" << 0 << "\n\n";

    t = clock();

    ctr = cpy = 0;

    t = clock();

    vector<vector<Pixel>> img2(n);

    for (int y = 0; y < n; ++y)

    img2[y].reserve(n);

    for (int y=0; y<n; ++y)

    for (int x=0; x<n; ++x)

    img2[y].push_back(c);

    cout << "img2 " << clock()-t << "\n";

    cout << "ctr " << ctr << " cpy " << cpy << " loop=" << n*n << "\n\n";

    ctr = cpy = 0;

    t = clock();

    Pixel** img3 = new Pixel*[n];

    for (int y = 0; y < n; ++y) img3[y] = new Pixel[n];

    cout << "img3 " << clock()-t << "\n";

    cout << "ctr=" << ctr << " cpy=" << cpy << " loop=" << n << "\n\n";

    for (int y = 0; y < n; ++y) delete [] img3[y];

    delete [] img3;

    }

    system("pause");

    return 1;

    }

    2013-12-01 07:05:20 補充:

    我補充一下, 避免我之前意見的誤導

    主要以實驗觀察

    ctr, cpy, assign, loop 在 vector < vector < > > 使用方式的成本

    也一併看 1D, 2D array 的 access 成本

    code 參考

    http://ideone.com/qSW5fo

    http://ideone.com/4w1yqY

    (VC2010, release, 完全最佳化 /ox)

    2013-12-01 07:09:55 補充:

    // output

    img1 50 <= (1)

    img2 57 <= (2)

    img3 45 <= (3)

    img4 16 <= (4)

    img1[y][x]= 7 <= (5)

    img3[y][x]= 6 <= (6)

    img4[y*n+x]= 10 <= (7)

    2013-12-01 07:14:24 補充:

    (1) vector < vector < Pixel > > img1 (n, vector < Pixel > (n) )

    (2) vector < vector < Pixel > > img2 (n); reserve then push

    (3) Pixel ** img3

    (4) Pixel * img4

    (1), (2), (3), (4) 表示不同的動態 "初始化" n x n Pixel 的方式. output 數字為完成時間.

    可以看出 (1) (2) 時間上差不多, (4) 最快.

    2013-12-01 07:17:32 補充:

    但如果要作任何一個存取 img[y][x] 的行為,

    (5) 對 vector < vector < Pixel** > > 存取

    (6) 對 Pixel** 存取

    (7) 對 Pixel* 存取

    大圖時, (5) 比 (6) 稍微多一些, 但 (7) 在 address operation 上的 overhead 大於其他.

    2013-12-01 07:20:56 補充:

    而打開 counter, 看初始化的成本

    img1 57. ctr=2048 cpy=4196352 loop=0

    img2 61. ctr=0 cpy=4194304 loop=4194304

    img3 46. ctr=4194304 cpy=0 loop=2048

    img4 24. ctr=4194304 cpy=0 loop=0

    2013-12-01 07:29:25 補充:

    其實初始化成本的確很大. 所以版大若是用 vector < vector < > > 作 image copy,以 preserve 避開初始化, 再 push Pixel 是對的.

    (1) Ctr = n, copy = n + Nixon, loop = 0

    (2) ctr = 0, cpy = nxn, loop = nxn

    (3) ctr = nxn, cpy = 0, loop = n

    (4) ctr = nxn, cpy = 0, loop = 0

    2013-12-01 07:31:54 補充:

    而 (1) 最佳化後, 速度並非總是比 (2) 快.

    所以需要初始化時, 像生成一張黑圖, 白圖, 用 reserve 再 push 也 ok, 只是 code 很冗長, 有 loop 成本, 也有 cpy 成本, 並非版大原先想的, 沒有 memory copy 的成本.

    2013-12-01 07:38:50 補充:

    回到版大的 Q1, Q2, Q3

    Q1. reserve 過不會有 memory copy ?

    不, 因為 n*n 次 push, 所以還是有 n*n 次 cpy 和 n*n loop overhead.

    但可以避開 ctr 是真的. 所以 image copy, 最適合 reserve 再 push

    2013-12-01 07:46:01 補充:

    Q2. 對動態 w*h image, 若不用 1D array 模擬 2D array 該怎麼作?

    有 (1)(2)(3) 種. 對 2D image filter, 個人觀點不論哪種 2D array 都比 1D array 簡單又好. 1D 的 address 運算成本太高. OpenCV Mat 內部是 1D array, 所以 at(y,x) 效率最低, 手冊也建議改用 row pointer

    2013-12-01 07:47:32 補充:

    Q3. vector< vector < Pixel > > img (height, vector < Pixel > (width) ); 怎麼讓初始化為255

    這樣就可

    Pixel white; white.x = white.y = white.z = 255;

    vector< vector < Pixel > > img (height, vector < Pixel > (width, white) );

  • Anonymous
    7 years ago

    還是要去 http://aaashops.com/ 品質不錯,老婆很喜歡。

    仿凉叿勈

  • 7 years ago

    // 2D array

    Pixel **img = new *Pixel[height];

    for (int i = 0; i < height; ++i) img[i] = new Pixel[width];

    或用

    vector< vector < Pixel > > img (height, vector < Pixel > (width) );

    成本應該相同吧?

    我會用vector, 就是因為我不需要手動delete, 謝謝你的幫忙, 如果OK,

    請您發至回答區, 我將選擇最佳解.

    2013-11-30 23:02:38 補充:

    謝謝~

    Tai 你好猛!!

    2013-12-01 15:34:13 補充:

    感謝幫助, 我後來全部都改為,

    color{

    unsigned char BGR[3];

    };

    Construction:

    color** image=new color*[n];

    for(int t=0; t

    2013-12-01 15:36:09 補充:

    真的快蠻多, 當n=4096, 建構只需不到1sec, 解構也是.

    然而用vector的方式, 建構會delay高達3~4秒, 解構delay甚至要數分鐘(以上).

    除非直接將程式強制終止(整個process占用的memory, 全部一起歸還)

  • 7 years ago

    vector是dynamically allocated.

    method2的意思可能是

    struct Pixel { ... };

    Pixel[4096][4096];

    理論上method2效率比較好,

    但程式會寫死, 因為影像大小不一定全都是4096p

    "聽說"編譯器若選擇release且有開最佳化的話, 效率不會差太多.

    2013-11-30 15:30:44 補充:

    int n = 4096;

    Pixel arr[n][n];

    這樣寫, n是dynamic才決定的, 編譯當然過不了.

    你要寫成

    Pixel arr[4096][4096];

    或是

    const int n = 4096;

    Pixel arr[n][n];

    就會編譯過的了.

    所謂dynamic就是執行期才能決定,

    反過來非dynamic就是編譯期就可決定.

    2013-11-30 15:44:56 補充:

    我在2F寫錯了, 不是Pixel[4096][4096];

    而是Pixel arr[4096][4096];

    "請問這樣宣告還會去dynamical allocated?"

    Pixel arr[4096][4096]這是static allocation.

    std::vector裡是用dynamic allocation實作的.

    2013-11-30 19:32:07 補充:

    reserve是要求vector配置指定的capacity.

    例如vector< int >某情況下可能capacity是20,

    相當於內部有個int *p_old = new int[20];

    但是裡面放的元素不一定是20個, 可能是0~20個, 可以呼叫size()查,

    2013-11-30 19:35:05 補充:

    若元素已經20個, 再呼叫push_back(),

    vector就必須調整capacity, 例如變成40,

    相當於要重新配置int *p_new = new int[40];

    把舊的p_old指向的資料移到新的p_new, 然後把p_old delete掉.

    再把元素放到第21個位置, 這時size()是21, 而capacity()是40.

    以上選擇capacity的策略是我亂說的, 實際上看編譯器怎麼作.

    若你已知vector大概會使用多少size,

    可事先呼叫reserve選擇足夠的capacity,

    可以避免中途push_back()常常重新配置.

    2013-11-30 19:40:51 補充:

    上面說new int[20], new int[40]只是說明用的,

    實際上可能不是直接用new的,

    可能只是allocate, 沒有作construct.

Still have questions? Get your answers by asking now.