Die effizienteste Ordnung der Indizes im Vektor des Vektors in C++

Question

Dies ist in erster Linie eine konzeptionelle C++ - Frage. Wenn ich eine bestimmte Matrix (gespeichert als Vektor von Vektoren) habe, auf die ich zugreifen muss, deren Größen in jeder Dimension sehr unterschiedlich sind. Ich habe viele Schritte, in denen ich die größere Dimension durchlaufe und Operationen in der kleineren Dimension durchführe. Ich frage mich, aus der Sicht der Effizienz hinsichtlich Zeit und Operationen auf dieser Matrix zuzugreifen, die von den beiden folgenden Beispielen wären effizienter:

Organisation 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]; 

Organisation 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]; 

im zweiten Beispiel es wie jeder würde ein Eintrag gesetzt scheint schneller geladen werden, sondern um über die j Dimension zu summieren, dann würden Sie 10-mal im Speicher springen per i den entsprechenden j Eintrag Iteration finden .

Im ersten Beispiel scheint es, als würde das Laden von A langsamer sein, aber dann sind alle Einträge in der unteren Dimension zur Summe verfügbar.

Neugierig, danke für Ihre Hilfe!

Answer 1

Ich denke, einen linearen Adressraum eher als ein Vektor von Vektoren Ihnen den besten Cache Ort geben:

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

}