Efficiently inserting column/row into a matrix stored in row/col-major vector in-place

Question

It's not hard to efficiently insert row or column into a matrix stored in a row- or col-major (respectively) vector. The problem of inserting row into a col-major vector or column into a row-major vector is slightly more interesting.

For example, given a 2x3 matrix stored in row-major in vector:

1 2 3    <=>    1 2 3 4 5 6 
4 5 6

and a column 7 8 that is inserted before after column 1 in the original matrix, we get:

1 7 2 3    <=>    1 7 2 3 4 8 5 6 
4 8 5 6

[Inserting a row into a col-major vector is similar.]

The sample setup in C++:

auto m = 2; // #rows
auto n = 3; // #cols
// row-major vector
auto x = std::vector<double>{1,2,3,4,5,6};

auto const colIndex = 1;
auto const col = std::vector<double>{7,8};
// insert column {7,8} into the 2nd position
// =>{1,7,2,3,4,8,5,6}

There could be various options to achieve this algorithmically and in C++, but we're looking for the efficiency and scalability to large matrices and multiple inserts.

The first obvious option that I can think of is to use std::vector<double>::insert to insert new elements to the correct positions:

//option 1: insert in-place
x.reserve(m*(n+1));
for(auto i = 0; i < col.size(); i++)
   x.insert(begin(x) + colIndex + i * (n + 1), col[i]);

, which is valid but extremely slow even for moderate data sizes because of the resizing and shifting on each iteration.

Another, more direct option is to create another vector, populate all the columns in the ranges [0,colIndex),colIndex,(colIndex,n+1], and swap it with the original vector:

// option 2: temp vec and swap
{
    auto tmp = std::vector<double>(m*(n+1));

    for(auto i = 0; i < m; i++)
    {
        for(auto j = 0; j < colIndex; j++)
            tmp[j + i * (n + 1)] = x[j + i * n];

        tmp[colIndex + i * (n + 1)] = col[i];

        for(auto j = colIndex + 1; j < n + 1; j++)
            tmp[j + i * (n + 1)] = x[(j - 1) + i * n];
    }

    std::swap(tmp, x);
};

This is much faster than the option 1, but requires extra space for the matrix copy and iterating over all elements.

Are there any other ways to achieve this that would beat the above in speed/space or both?

Example code on ideone: https://ideone.com/iXrPfF

Answer 1

This version is likely to be much faster, especially at scale, and could be the basis for further micro-optimization (if [and only if] really necessary):

// one-time reallocation of the vector to get space for the new column
x.resize(x.size() + col.size());

// we'll start shifting elements over from the right
double *from = &x[m * n];
const double *src = &col[m];
double *to = from + m;

size_t R = n - colIndex; // number of cols left of the insert
size_t L = colIndex;     // number of cols right of the insert

while (to != &x[0]) {
    for (size_t i = 0; i < R; ++i) *(--to) = *(--from);
    *(--to) = *(--src); // insert value from new column
    for (size_t i = 0; i < L; ++i) *(--to) = *(--from);
}

ideone

This doesn't require any temporary allocation and aside from possible micro-optimizations of the loop it's probably about as fast as it gets. To understand how it works, we can start by observing that the bottom-right element of the original matrix is being shifted m elements to the right in the source vector. Working backwards from the last element, at some point a value from the inserted column vector gets inserted, and subsequent elements from the source vector are now shifted m - 1 only elements to the right. Using that logic we simply construct a 3-phase loop that works from right to left on the source array. The loop iterates m times, once for each row. The three phases of the loop, corresponding to its three lines of code, are:

1. Shift row elements that are "to the right" of the insertion point.
2. Insert the row value from the new column.
3. Shift row elements that are "to the left" of the insertion point (shifting one less place than in phase 1).

There's also serious room for improvement in the naming of the variables, and the algorithm should certainly be encapsulated in its own function with proper input parameters. One possible signature would be:

void insert_column(std::vector<double>& matrix,
    size_t rows, size_t columns, size_t insertBefore,
    const std::vector<double>& column);

From here there's further room for improvement in making it generic using templates.

And from there, you might observe that the algorithm has possible application beyond matrices. What's really happening is that you're "zippering" two vectors together with a skip and an offset (i.e., starting at element i, insert an element from B into A after every n'th element).

Answer 2

so what I would go with is something like (completely untested (tm))

x.resize(x.size() + col.size());

for (size_t processed = 0; processed < col.size(); ++processed) {
    // shift the elements for row n (starting at the end) 
    // to their new location
    auto start = x.end()-(processed+1) * rowSize;
    auto end = start + rowSize;
    auto middle = end - (col.size()-processed);
    std::rotate(start, middle, end);

    // replace one of the default value items to be the new value
    x[x.size()- rowSize*(1+processed)] = col[col.size()-processed-1];
}

The idea being that you go from [1,2,3,4,5,6] & adding [a,b,c]

Resize: [1,2,3,4,5,6,x,x,x]

First loop shift: [1,2,3,4,x,x,x,5,6]

First loop replace [1,2,3,4,x,x,c,5,6]

Second loop shift [1,2,x,x,3,4,c,5,6]

and so on.

Since std::rotate is linear, and each item only ever gets moved once; this should also be linear.

This differs to your option #1 in that every time you inserted, you have to move everything afterwards; meaning that the last x elements are shifted col.size() times.

Answer 3

An alternate solution can be transpose followed by insertion and transpose again. However, the in-place transpose in non-trivial (https://en.wikipedia.org/wiki/In-place_matrix_transposition). See the implementation here https://stackoverflow.com/a/9320349