Cách hiệu quả nhất để khởi tạo một vector 3D là gì?

Question

Tôi có một vector chuỗi 3D trong C++:

vector<vector<vector<string>>> some_vector 

Rằng tôi đang cố gắng là để tìm một phương pháp nhanh để cấp phát bộ nhớ cho nó.

Tôi cố gắng để xác định nó bằng hai phương pháp khác nhau như sau:

#include<vector> 
#include<iostream> 
#include<ctime> 
using namespace std; 

#define DIM1 100 
#define DIM2 9 
#define DIM3 120 

int main() 
{ 
    clock_t t1_start = clock(); 
    vector<vector<vector<string>>> vec1(DIM1, vector<vector<string>>(DIM2, vector<string>(DIM3))); 
    clock_t t1_end = clock(); 
    double diff1 = (t1_end - t1_start)/double(CLOCKS_PER_SEC); 

    clock_t t2_start = clock(); 
    vector<vector<vector<string>>> vec2; 
    vec2.resize(DIM1); 
    for(int i = 0; i < DIM1; i++) 
    { 
     vec2[i].resize(DIM2); 
     for(int j = 0; j < DIM2; j++) 
      vec2[i][j].resize(DIM3); 
    } 
    clock_t t2_end = clock(); 

    double diff2 = (t2_end - t2_start)/double(CLOCKS_PER_SEC); 

    cout<<"1st definition used time: "<<diff1<<"s"<<endl; 
    cout<<"2nd definition used time: "<<diff2<<"s"<<endl; 
} 

Tôi hy vọng rằng phương pháp đầu tiên (vec1) có thể là nhanh hơn so với một trong 2 (vec2).

Nhưng hóa ra là phương pháp thứ nhất chậm hơn nhiều so với lần thứ 2. Trên máy tính của tôi, phương pháp thứ nhất sử dụng 0.245 giây, trong khi phương pháp thứ 2 sử dụng 0.152 giây.

Hơn nữa, khi tôi chuyển kiểu dữ liệu thành int, số thứ nhất mất 0,058 giây và số thứ hai mất 0,004.

Tôi có thể biết nguyên nhân gây ra sự khác biệt như thế nào không? Và có cách nào tốt hơn để phân bổ bộ nhớ cho một vector 3D?

Rất cám ơn trước.

Answer 1

Tôi nghĩ tôi sẽ tối ưu hóa nó bằng cách phân bổ một khối bộ nhớ lớn thay vì nhiều bộ nhớ nhỏ. Cái này chỉ là 2D thay vì 3D, nhưng cung cấp cho các ý tưởng cơ bản:

template <class T> 
class matrix { 
    size_t columns_; 
    std::vector<T> data; 
public: 
    matrix(size_t columns, size_t rows) : columns_(columns), data(columns*rows) {} 

    T &operator()(size_t column, size_t row) { return data[row*columns_+column]; } 
}; 

Đối với 3D, bạn sẽ cần phải đối phó với "máy bay" (hoặc một cái gì đó) cùng với hàng và cột, nhưng ý tưởng cơ bản là khá giống nhau.

Answer 2

Tôi có thể biết nguyên nhân gây ra sự khác biệt như thế nào không?

Phiên bản đầu tiên xây dựng vectơ 2 chiều bằng cách sao chép véc tơ 1-d, sau đó tạo vectơ 3 chiều bằng cách sao chép. Điều này có thể chậm hơn so với thay đổi kích cỡ các vectơ mà không cần sao chép. Tuy nhiên, tôi hy vọng rằng sự khác biệt sẽ không đáng kể nếu bạn đang xây dựng với tối ưu hóa.

Và có cách nào tốt hơn để cấp phát bộ nhớ cho một véc tơ 3D không?

Có thể tốt hơn khi sử dụng một mảng liền kề duy nhất, được bao bọc trong lớp cung cấp trình tiếp cận đa chiều. Điều này sẽ làm cho phân bổ đơn giản hơn nhiều, và cũng sẽ tránh một số dereferencing con trỏ khi truy cập các phần tử (với chi phí của một chút số học). Một cái gì đó như thế này:

template <typename T> 
class vector3d { 
public: 
    vector3d(size_t d1=0, size_t d2=0, size_t d3=0, T const & t=T()) : 
     d1(d1), d2(d2), d3(d3), data(d1*d2*d3, t) 
    {} 

    T & operator()(size_t i, size_t j, size_t k) { 
     return data[i*d2*d3 + j*d3 + k]; 
    } 

    T const & operator()(size_t i, size_t j, size_t k) const { 
     return data[i*d2*d3 + j*d3 + k]; 
    } 

private: 
    size_t d1,d2,d3; 
    std::vector<T> data; 
}; 

Answer 3

Khi bạn khởi tạo vectơ vectơ trong phương pháp thứ nhất, một vector tạm thời được phân bổ và sau đó được sao chép vào vectơ ngoài số lần yêu cầu. Điều này có nghĩa là bạn có một phân bổ bổ sung không cần thiết và các phần tử mới được khởi tạo bằng cách sao chép giá trị của chúng từ một cấu trúc dữ liệu khác, sử dụng nhiều truy cập bộ nhớ hơn.

Thay đổi kích thước các vectơ theo phương pháp thứ hai sẽ xấu hơn nhưng tránh phân bổ bổ sung. Hơn nữa các phần tử mới được tạo bởi hàm tạo mặc định và không cần phải sao chép từ các vectơ khác. Điều này cũng sẽ nhanh hơn.

Nếu tốc độ quan trọng (và có thể không, tối ưu hóa sớm và tất cả điều đó), thì bạn phải sử dụng phương pháp thứ hai (HOẶC phân bổ một khối theo đề xuất của các câu trả lời khác). Tôi không tin rằng một trình biên dịch có thể đơn giản là "tối ưu hóa" sự mất hiệu quả của phương pháp đầu tiên.

Answer 4

Để khởi tạo một vector 3D chuỗi bạn phải khởi tạo cấu trúc vector cho mỗi chiều cùng một lúc và cho mỗi chỉ số, ví dụ:

vector<vector<vector<string> > > myvector; //declare the 3D vector 
    for(k=0; k<3; k++) 
    { 
    myvector.push_back(vector<vector<string> >()); //initialize the first index with a 2D vector 
    for(i=0; i<4; i++) 
    { 
     myvector[k].push_back(vector<string>()); //initialize the 2 index with a row of strings 
     for(j=0; j<4; j++) 
     { 
     result = " whatever you want to insert in the vector element"; 
     myvector[k][i].push_back(result); //fulfill the last index regularly 
     } 
    } 
    }