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++中矢量向量中索引的最有效排序

回答

相關問題