C++中矢量向量中索引的最有效排序

这主要是一个C++概念问题。如果我有一个特定的矩阵（作为向量的向量存储），我必须访问它，每个维度的大小是非常不同的。我有很多步骤，我遍历更大的维度并在更小的维度上执行操作。我是从效率的观点来看，不知道相对于访问时间和操作在此矩阵，其中下面两个例子将是更有效的：C++中矢量向量中索引的最有效排序

组织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维度，您将在每次迭代中跳过10次内存来查找相应的j条目。

在第一个例子中，看起来加载A会比较慢，但是下面维度中的所有条目都可用于求和。

对此感到好奇，感谢您的帮助！

来源

2016-05-14 Siddharth Krishnamoorthy

我觉得一个线性地址空间，而不是矢量会给你最好缓存局部性的载体：

#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); 
    } 

}

来源

2016-05-14 22:54:32

谢谢！如果我对它的理解正确，那么您将“矢量化”矢量转化为线性矢量......我可以继续尝试。就我的知识而言，如果一个人使用二维数组，而我被限制为循环上面显示的方式（i = 0：1000，那么j = 0：10）......两个中的哪一个以上可能会更快？ –

@SiddharthKrishnamoorthy在这种情况下，可能是让你在更小维度上进行线性运行的原因 - 因为内存被提取到缓存中的方式。 –

谢谢你的帮助！ –

C++中矢量向量中索引的最有效排序

回答

相关问题