这主要是一个 C++ 概念性问题。如果我有一个必须访问的特定矩阵(存储为 vector 的 vector ),它在每个维度上的大小都非常不同。我有很多步骤,我循环遍历较大的维度并在较小的维度上执行操作。我想知道从访问时间和对该矩阵的操作的效率的角度来看,以下两个示例中哪个更有效:
组织 1:
A=vector<vector<float>>(1000,vector<float>(10,0.0));
sumAcrossSmallerDimension=vector<float>(1000,0.0);
for(int i=0;i<1000;i++)
for(int j=0;j<10;j++)
sumAcrossSmallerDimension[i]+=A[i][j];
组织 2:
A=vector<vector<float>>(10,vector<float>(1000,0.0));
sumAcrossSmallerDimension=vector<float>(1000,0.0);
for(int i=0;i<1000;i++)
for(int j=0;j<10;j++)
sumAcrossSmallerDimension[i]+=A[j][i];
在第二个示例中,似乎每个集合 A 条目的加载速度都更快,但为了对 j 维度求和,您需要在每次 i 迭代时在内存中跳转 10 次以找到相应的 j 条目。
在第一个示例中,加载 A 似乎会更慢,但较低维度中的所有条目都可以随时求和。
对此感到好奇,感谢您的帮助!
最佳答案
我认为线性地址空间而不是 vector 的 vector 会给你最好的缓存位置:
#include <memory>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>
struct vv
{
vv(std::size_t rows, std::size_t columns, double init)
: _rows(rows), _columns(columns), _size(_rows * _columns)
, _pdata(std::make_unique<double[]>(_size))
{
std::fill(_pdata.get(), _pdata.get() + _size, init);
}
const double* operator[](std::size_t i) const {
return std::addressof(_pdata.get()[i * _columns]);
}
double rowSum(std::size_t i) const {
auto p = (*this)[i];
return std::accumulate(p, p + _columns, 0.0, std::plus<>());
}
std::size_t _rows, _columns, _size;
std::unique_ptr<double[]> _pdata;
};
int main()
{
vv v(1000, 10, 10.0);
auto sumAcrossSmallerDimension = std::vector<double>(1000,0.0);
for(std::size_t i = 0 ; i < 1000 ; ++i)
{
sumAcrossSmallerDimension[i] += v.rowSum(i);
}
}
关于c++ - C++中 vector vector 中索引的最有效排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37231291/