CODEWITHSUNDEEP
c++arraysmatrixpartitioningsub-array
user2471711
user2471711

Reputation: 85

partition a 2D array without looping c++

Im fairly new to c++ and am trying to program strassen's algorithm to multiply matrices. Part of the algorithm requires me to partition a matrix into four parts e.g

4 5 6 7
6 7 8 9
1 2 3 4
2 3 5 6

partitioned:

4 5   6 7
6 7   8 9

1 2   3 4
2 3   5 6

(each part is then used again recursively and partitioned). I want to partition the matrices without looping and copying the data from the original matrix (as this would take more time). The book i am reading says the matrices are partitioned using 'index calculations, identifying a submatrix by a range of row indices and a range of column indices of the original matrix.i am not sure what is meant by this.

Also, im not sure whether i should be using 2D arrays or vectors? Ive seen alot of people recommending vectors but ive already written everything so far in 2D arrays so im hoping what i want is possible with 2D arrays.

p.s it can be assumed the dimensions of the matrices will always be a power of 2 and be nxn (square). Also, i have seen alot of questions similar to this but none of them actually have the solution i am looking for.

Thanks

Upvotes: 4

Views: 1116

Answers (1)

6502
6502

Reputation: 114579

You can create a matrix class that supports directly sub-matrices as views:

template<typename T>
struct Matrix {
    int rows, cols, stride;
    std::vector<T> data; // Possibly empty for a view
    T *ptr;

    // A fresh matrix (owning its data)
    Matrix(int rows, int cols)
        : rows(rows), cols(cols), stride(cols),
          data(rows*cols),
          ptr(&data[0])
    {
    }

    // A view of a sub-matrix (pointing to the original data!)
    Matrix(Matrix& m, int row0, int col0, int rows, int cols)
        : rows(rows), cols(cols), stride(m.stride),
          ptr[&m(row0, col0)]
    {
    }

    T& operator()(int row, int col) {
        return ptr[row*stride + col];
    }

    ...
};

Of course you need to ensure that views don't outlive the owning matrix and you need to pay attention to what you want to mean to copy a view object if that operation is not forbidden.

Adding explicit operations like transforming a view into an owning matrix can be useful (if a copy constructor is not going to do that).

Upvotes: 1

Related Questions