c++ - 有效地将列/行插入到存储在行/列主 vector 中的矩阵中

Question

高效地将行或列插入存储在行中的矩阵并不难- 或 col-major(分别) vector 。将行插入列优先 vector 或将列插入行优先 vector 的问题稍微有趣一些。

例如，给定一个 2x3 矩阵，以行优先方式存储在 vector 中:

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

和一列 7 8在原始矩阵的第 1 列之后插入之前，我们得到:

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

[将一行插入列主 vector 中是类似的。]

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}

可能有多种选择可以通过算法和 C++ 实现此目的，但我们正在寻找大型矩阵和多个插入的效率和可扩展性。

我能想到的第一个显而易见的选择是使用 std::vector<double>::insert将新元素插入到正确的位置:

//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]);

，这是有效的，但非常即使对于中等数据大小也很慢，因为每次迭代都会调整大小和移动。

另一个更直接的选择是创建另一个 vector ，填充范围 [0,colIndex),colIndex,(colIndex,n+1] 中的所有列。 ，并将其与原始 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);
};

这比选项 1 快很多，但需要额外的空间用于矩阵复制和遍历所有元素。

是否有任何其他方法可以在速度/空间或两者上击败上述方法？

ideone 上的示例代码:https://ideone.com/iXrPfF

Answer 1

这个版本可能会快得多，尤其是在规模上，并且可以作为进一步微优化的基础(如果[且仅当]确实有必要):

// 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

这不需要任何临时分配，除了可能对循环进行微优化外，它可能已经达到了最快的速度。要了解它的工作原理，我们可以从观察原始矩阵的右下角元素在源 vector 中向右移动 m 个元素开始。从最后一个元素向后工作，在某个时候插入列 vector 中的值被插入，并且源 vector 中的后续元素现在仅向右移动 m - 1 个元素。使用该逻辑，我们只需构建一个在源阵列上从右到左工作的三相环路。循环迭代 m 次，每行一次。循环的三个阶段，对应它的三行代码，分别是:

1. 移动插入点“右侧”的行元素。
2. 插入新列中的行值。
3. 移动插入点“左侧”的行元素(比阶段 1 少移动一位)。

变量的命名也有很大的改进空间，算法当然应该封装在自己的函数中，并带有适当的输入参数。一种可能的签名是:

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

从这里开始，在使用模板使其通用化方面还有进一步的改进空间。

从那里，您可能会观察到该算法的应用可能超出矩阵范围。真正发生的是，您将两个 vector “压缩”在一起，并加上一个跳跃和一个偏移量(即，从元素 i 开始，将 B 中的一个元素插入到 A 在每个 n 元素之后)。