logo标签列表

什么是初始化3D向量的最有效方法？

c++performancevector
11

我在C++中有一个3D字符串向量：

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)更快。

但事实证明，第一种方法比第二种方法慢得多。在我的机器上，第一种方法用了0.245秒，而第二种方法只用了0.152秒。

此外，当我将数据类型切换为int时，第一种方法只用了0.058秒，而第二种方法则只用了0.004秒。

请问这是什么原因造成的差别？是否有更好的方法来分配3D向量的内存空间？

提前感谢您的帮助。

2
你正在使用优化构建吗？ - juanchopanza
3
如果尺寸固定不变，为什么不使用std::array<std::array<std::array<std::string, DIM3>, DIM2>, DIM1>？ - dchhetri
这可能是因为在第一次调用时可能会生成更多的副本，而在第二次调用时则不同。 - dchhetri
如果您交换测试顺序，会如何影响计时？（并确保启用了优化）。考虑使用一个更好的基准测试工具，该工具使用高精度计时器并运行多个迭代以平滑各种与缓存相关和外部环境影响。可以考虑使用 better benchmarking tool。 - Cameron
@jeffamaphone 谢谢回复。那么您会推荐哪种数据结构呢？ - ChangeMyName
显示剩余3条评论
6个回答
17

请问造成这种差异的原因是什么？

第一种版本通过复制1-d向量来构建2-d向量，然后通过复制2-d向量来构建3-d向量。这可能比不复制调整向量大小更慢。但是，我希望如果您使用优化编译，则差异将可以忽略不计。

有更好的方法来为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 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;
};
边界检查通常是使用向量的原因。在您的运算符中添加断言以确保每个索引都在其维度以下是一个好主意。 - Neil Kirk
1
@NeilKirk：确实，这个可能需要一个范围检查的at函数和其他一些细节，才能更好地实现自己的容器。 - Mike Seymour
4

我认为可以通过分配一个大内存块而不是许多小内存块来进行优化。这个示例只涉及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，您需要处理“平面”（或类似物）以及行和列，但基本思想基本相同。

4

我对Mike Seymour的代码添加了一些功能，例如动态调整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)
2

要初始化一个三维字符串向量，您应该逐一为每个维度初始化向量结构，并为每个索引初始化，例如：

  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
      } 
    }
  }
0

这里有一个向量的各种维度示例，如果有人在意的话。我知道当我刚开始学习时，给多维向量赋初值是一件很麻烦的事情，因为我找不到任何例子。

// 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";
    }
    

}
请在您的回答中提供更多细节。目前的描述不够清晰，难以理解您的解决方案。 - Community
清单已经完成，复制粘贴并使用调试器跟踪它以了解其操作。我只是提供了一个示例，说明如何在代码中创建1d、2d、3d或4d向量以及如何分配初始值（将值更改为您想要的任何值），然后如何通过for循环逐步打印出这些值。这里的主要重点是展示如何将初始值分配给3d和4d向量。我知道有时候初学者会搜索这个问题...我在开始时也是这样，这可能会让初学者感到沮丧。所以我想提供一个简单的例子。 - Da Guest
0

当你在第一种方法中初始化一个向量的向量时，会分配一个临时向量，然后将其复制到外部向量中所需的次数。这意味着你有一个不必要的额外分配，并且新元素通过从另一个数据结构复制它们的值来初始化，这使用了更多的内存访问。

根据第二种方法调整向量大小更加丑陋，但避免了额外的分配。此外，新元素是通过默认构造函数创建的，不需要从其他向量复制。这也会更快。

如果速度很重要（也许并不重要，过早优化等等），那么你必须使用第二种方法（或者像其他答案建议的单块分配）。我不相信编译器可以简单地“优化”掉第一种方法的低效率。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接