C++如何将 vector 表示为矩阵并转置它？

Question

我有一个大小为n的 vector ； n 是 2 的幂。我需要将此 vector 视为矩阵 n = R*C。然后我需要转置矩阵。

例如，我有 vector :[1,2,3,4,5,6,7,8]

我需要找到 R 和 C。在本例中它将是:4,2。并将 vector 视为矩阵:

[1,2]
[3,4]
[5,6]
[7,8]

将其转置为:

[1, 3, 5, 7]
[2, 4, 6, 8]

转置后 vector 应为:[1, 3, 5, 7, 2, 4, 6, 8]

是否有现有算法可以执行就地非方矩阵转置？我不想重新发明轮子。

我的 vector 非常大，所以我不想创建中间矩阵。我需要一个就地算法。性能非常重要。

• 所有修改都应在原始 vector 中完成。理想情况下，算法应该适用于适合 CPU 缓存的 block 。
• 由于内存局部性，我无法使用迭代器。所以我需要真正的换位。
• 矩阵是 2x4 还是 4x2 并不重要

Answer 1

问题可以分为两部分。首先，找到 R 和 C，然后 reshape 矩阵。这是我会尝试做的事情:

由于 n 是 2 的幂，即 n = 2^k 那么如果 k 是偶数，我们有:R=C=sqrt(n)。如果 k 是奇数，则 R = 2^((k+1)/2) 和 C=2^((k-1)/2 )。

注意:既然你提到你想避免使用额外的内存，我对原来的答案做了一些版本。

计算R和C的代码如下:

void getRandC(const size_t& n, size_t& R, size_t& C)
{
    int k = (int)log2(double(n)),
        i, j;

    if (k & 1)  // k is odd
        i = (j = (k + 1) / 2) - 1;
    else
        i = j = k / 2;

    R = (size_t)exp2(i);
    C = (size_t)exp2(j);
}

需要 C++11。对于第二部分，如果您想保留原始 vector :

void transposeVector(const std::vector<int>& vec, std::vector<int>& mat)
{
    size_t R, C;
    getRandC(vec.size(), R, C);

    // first, reserve the memory
    mat.resize(vec.size());

    // now, do the transposition directly
    for (size_t i = 0; i < R; i++)
    {
        for (size_t j = 0; j < C; j++)
        {
            mat[i * C + j] = vec[i + R * j];
        }
    }
}

而且，如果你想修改原始 vector 并避免使用额外的内存，你可以这样写:

void transposeInPlace(std::vector<int>& vec)
{
    size_t R, C;
    getRandC(vec.size(), R, C);

    for (size_t j = 0; R > 1; j += C, R--)
    {
        for (size_t i = j + R, k = j + 1; i < vec.size(); i += R)
        {
            vec.insert(vec.begin() + k++, vec[i]);
            vec.erase(vec.begin() + i + 1);
        }
    }
}

参见the live example