c++ - C++中 vector vector 中索引的最有效排序

Question

这主要是一个 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 似乎会更慢，但较低维度中的所有条目都可以随时求和。

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

Answer 1

我认为线性地址空间而不是 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);
  }

}