C++ векторизация вектора векторов

Question

У меня есть код, который использует vector<vector<>> для хранения результатов расчета.

С помощью бенчмаркинга я обнаружил, что это мешает моему векторизации кода, хотя я обращаюсь к элементам с соответствующим C-шагом.

Я пытаюсь создать структуру данных, которая будет векторизовывать и улучшать производительность моего кода.

Я прочитал несколько сообщений здесь, и некоторые из них упомянули о создании класса, который имеет 2 отдельных вектора внутри: 1 для хранения данных смежно, а другой для хранения индексов, обозначающих начало нового столбца/строки из оригинал 2D vector<vector>. По сути, он разложил 2D-массив на 1D и использовал бы «вспомогательный» вектор, чтобы обеспечить правильную индексацию.

Я забочусь о том, что я также читал, что векторизация обычно не происходит с косвенным индексированием, подобным этому, например, в общей схеме хранения сжатых строк для разреженных матриц.

Перед тем, как я пройду всю работу по ее реализации, кто-нибудь сталкивался с этой проблемой раньше и решил ее? Любые другие предложения или ресурсы, которые могли бы помочь?

Answer 1

Я написал небольшой класс матрицы, основанный на std::vector:

#include <vector> 

template <typename T> 
class MyMatrix { 
    public: 

    typedef T value_type; 
    struct RowPointer { 
     int row_index; 
     MyMatrix* parent; 
     RowPointer(int r,MyMatrix* p) : row_index(r),parent(p) {} 
     T& operator[](int col_index) { 
      return parent->values[row_index*parent->cols+col_index]; 
     } 
    }; 
    MyMatrix() : rows(0),cols(0),size(0),values(){} 
    MyMatrix(int r,int c) : rows(r),cols(c),size(r*c),values(std::vector<T>(size)){} 
    RowPointer operator[](int row_index){return RowPointer(row_index,this);} 

    private: 

    size_t rows; 
    size_t cols; 
    size_t size; 
    std::vector<T> values; 
}; 

Он может быть использован, как это:

MyMatrix<double> mat = MyMatrix<double>(4,6); 
mat[1][2] = 3; 
std::cout << mat[0][0] << " " << mat[1][2] << std::endl; 

Он по-прежнему пропускает много вещей, но я думаю, что это достаточно, чтобы проиллюстрировать идея уплощения матрицы. Из вашего вопроса это не было на 100% ясным, если ваши ряды имеют разные размеры, тогда шаблон доступа немного сложнее.

PS: Я больше не хочу менять ответ, но я бы никогда не использовал std::vector, чтобы снова построить матрицу. Векторы предлагают гибкость, которая не требуется для матрицы, которая обычно имеет одинаковое и фиксированное количество записей в каждой строке.