Каков наиболее эффективный способ инициализации трехмерного вектора?
У меня есть 3D-вектор строки в C++:
vector<vector<vector<string>>> some_vector
Я пытаюсь найти быстрый способ выделить для него память.
Я попытался определить это двумя различными методами следующим образом:
#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;
}
Я ожидаю, что первый метод (vec1) может быть быстрее, чем второй (vec2).
Но оказалось, что 1-й способ намного медленнее, чем 2-й. На моей машине первый метод использовал 0,245 секунды, а второй - 0,152 секунды.
Более того, когда я переключаю тип данных на int, первый занял 0,058 секунды, а второй - 0,004.
Могу ли я узнать, в чем причина такой разницы? И есть ли лучший способ выделить память для трехмерного вектора?
Спасибо заранее.
6 ответов
Могу ли я узнать, в чем причина такой разницы?
Первая версия создает 2-й вектор, копируя 1-й вектор, а затем создает 3-й вектор, копируя его. Это может быть медленнее, чем изменение размеров векторов без копирования. Однако я надеюсь, что разница будет незначительной, если вы строите с оптимизацией.
И есть ли лучший способ выделить память для трехмерного вектора?
Возможно, было бы лучше использовать один непрерывный массив, заключенный в класс, который предоставляет многомерные методы доступа. Это значительно упростит распределение и позволит избежать разыменования указателей при обращении к элементам (за счет небольшой арифметики). Что-то вроде этого:
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;
};
Я думаю, что я бы оптимизировал его, выделив один большой блок памяти вместо множества маленьких. Это только 2D вместо 3D, но дает основную идею:
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]; }
};
Для 3D вам нужно иметь дело с "плоскостями" (или чем-то еще) вместе со строками и столбцами, но основная идея почти такая же.
Я добавил несколько функций в код Майка Сеймура, таких как динамическое изменение размера трехмерного вектора и проверка доступа / назначения границ для вектора данных.
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 (i<=d1 && j<=d2 && k<=d3) ? data[i*d2*d3 + j*d3 + k]
: data.at(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];
}
void resize(const size_t _d1=0, const size_t _d2=0, const size_t _d3=0)
{
data.resize(_d1*_d2*_d3);
d1=_d1;
d2=_d2;
d3=_d3;
}
void shrink_to_fit()
{
data.shrink_to_fit();
}
const size_t length() const
{
return data.size();
}
const size_t capacity() const
{
return data.capacity();
}
const size_t x() const
{
return d1;
}
const size_t y() const
{
return d2;
}
const size_t z() const
{
return d3;
}
private:
size_t d1,d2,d3;
std::vector<T> data;
};
Применение:
vector3d<int> vec3d(2,2,2,31); //create 2x2x2 3d vector and fill it with 31
vec3d(1,1,2)=45; //assign 45 at vec3d(1,1,2)
vec3d.resize(2,2,1); //resize the vec3d to 2x2x1
vec3d(1,2,2)=67; //error (its out of bounds)
Чтобы инициализировать трехмерный вектор строки, вы должны инициализировать векторную структуру для каждого измерения по одному и для каждого индекса, например:
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
}
}
}
Когда вы инициализируете вектор векторов в первом методе, временный вектор выделяется, а затем копируется во внешний вектор необходимое количество раз. Это означает, что у вас есть дополнительное выделение, которое не нужно, и новые элементы инициализируются путем копирования их значения из другой структуры данных, которая использует больше обращений к памяти.
Изменение размеров векторов согласно второму методу более уродливо, но позволяет избежать дополнительного выделения. Кроме того, новые элементы создаются конструктором по умолчанию и не требуют копирования из других векторов. Это также будет быстрее.
Если скорость имеет значение (и, возможно, это не так, преждевременная оптимизация и все такое), то вы должны использовать второй метод (ИЛИ распределение по одному блоку, как предлагается другими ответами). Я не верю, что компилятор может просто "оптимизировать" неэффективность первого метода.
Вот пример различных размерностей векторов на тот случай, если кому-то не все равно. Я знаю, что когда я только начинал, было сложно найти, как задать начальные значения многомерным векторам, поскольку я не мог найти никаких примеров;
// This simple project demonstrates a single vector, a 2D vector, a 3D vector and a 4D vector in C++
//
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> myVector = { 0,1,2,3,4,5,6 };
vector<vector<int>> my2dVector = { {1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25},{0,-1,-2,-3,-4},{-6,7,22,-15,-25},{true,true,false,true,false} };
vector < vector < vector<int>>> my3dVector =
{
{
{1,2,3},
{4,5,6}, // plane 0
{7,8,9}
},
{
{-1,-2,-3},
{-4,-5,-6}, // plane 1
{-10,-22,36}
},
{
{129,212,999},
{0,0,1}, // plane 2
{false,true,false}
}
};
vector<vector<vector<vector<int>>>> my4dVector =
{
{ //Cube 0
{
{1,2,3},
{4,5,6}, // plane 0
{7,8,9}
},
{
{-1,-2,-3},
{-4,-5,-6}, // plane 1
{-10,-22,36}
},
{
{129,212,999},
{0,0,1}, // plane 2
{false,true,false}
}
},
{ //Cube 1
{
{10,2,-9},
{44,55,60}, // plane 0
{71,85,99}
},
{
{-561,-6562,-453},
{-14,-55,-76}, // plane 1
{-110,-212,316}
},
{
{729,812,456},
{40,10,17}, // plane 2
{true,true,false}
}
}
};
// 1D VECTOR..............
cout << "This is a 1D vector of size " << myVector.size () << "\n";
for (int i = 0; i < myVector.size (); i++)
{
cout << myVector[i] << "\t";
}
cout << "\n\n";
// 2D VECTOR..............
cout << "This is a 2D vector of size " << my2dVector.size () << " X " << my2dVector[0].size () << ".";
if (my2dVector.size () == my2dVector[0].size ()) cout << " This is a square matrix.";
cout << "\n ";
for (int i = 0; i < my2dVector[0].size (); i++)
{
cout << "C" << i << "\t";
}
cout << endl;
for (int i = 0; i < my2dVector.size (); i++)
{
cout << "Row: " << i << " -> ";
for (int j = 0; j < my2dVector[i].size (); j++)
{
if (my2dVector[i][j] >= 0 && my2dVector[i][j] <= 9) cout << " ";
cout << my2dVector[i][j] << "\t";
}
cout << endl;
}
cout << "\n\n";
// 3D VECTOR.................
cout << "This is a 3D vector of size " << my3dVector[0].size () << " X " << my3dVector[0][0].size () << " with " << my3dVector.size () << " planes.\n";
for (int i = 0; i < my3dVector.size (); i++)
{
cout << "Plane #" << i << "\n";
for (int j = 0; j < my3dVector[i].size (); j++)
{
for (int k = 0; k < my3dVector[i][j].size (); k++)
{
cout << my3dVector[i][j][k] << "\t";
}
cout << "\n";
}
}
cout << "\n\n";
//4D VECTOR.................
cout << "This is a 4D vector of size " << my4dVector[0][0].size () << " X " << my4dVector[0][0][0].size () << " with " << my4dVector[0].size () << " planes and " << my4dVector.size () << " cubes.\n";
for (int i = 0; i < my4dVector.size (); i++)
{
cout << "\nCUBE #"<< i<< " _________________\n";
for (int j = 0; j < my4dVector[i].size (); j++)
{
cout << "Plane #" << j << " |\n";
for (int k = 0; k < my4dVector[i][j].size (); k++)
{
for (int l = 0; l < my4dVector[i][j][k].size (); l++)
{
cout << my4dVector[i][j][k][l] << "\t";
}
cout << "|\n";
}
cout << "________________________|\n";
}
cout << "\n";
}
}