c ++如何将向量表示为矩阵并转置它？

Question

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

比如我有向量：[1,2,3,4,5,6,7,8]

我需要找到 R 和 C。在本例中为：4,2。并将向量视为矩阵：

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

将其转置为：

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

转置向量后应为：[1, 3, 5, 7, 2, 4, 6, 8]

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

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

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

Answer 1

由于您没有向我们提供任何代码，我能否建议一种不同的方法（我不知道它是否适用于您的特定情况）？

我会使用基于您的矩阵的算法自行将您的值转置到新矩阵中。由于性能是一个问题，这将更有帮助，因为您不必创建另一个矩阵。如果这适用于您。

有一个向量

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

创建矩阵

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

不使用其他矩阵重新排序向量

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

覆盖当前矩阵中的值（这样您就不必创建新矩阵）并根据当前矩阵对值重新排序。

按顺序添加值

R1 and C1 to transposed_vector[0]
R2 and C1 to transposed_vector[1]
R3 and C1 to transposed_vector[2]
R4 and C1 to transposed_vector[3]
R1 and C2 to transposed_vector[4]

以此类推

Answer 2

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

因为 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。对于第二部分，如果你想保留原始向量：

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];
        }
    }
}

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

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

Answer 3

对于非方阵表示，我认为这可能很棘手，不值得在不创建另一个平面向量的情况下进行平面向量转置。这是我想出的一个片段：

chrono::steady_clock::time_point start = chrono::steady_clock::now();
int i, j, p, k;
vector<int> t_matrix(matrix.size());
for(k=0; k< R*C ;++k)
{
    i = k/C;
    j = k - i*C;
    p = j*R + i;
    t_matrix[p] = matrix[k];
}
cout << chrono::duration_cast<chrono::milliseconds> chrono::steady_clock::now() - start).count() << endl;

这里，matrix 是平面向量，t_matrix 是 "transposed" 平面向量，R 和 C 分别是行和向量你找到了你的矩阵表示。

c ++如何将向量表示为矩阵并转置它？

c++ how to represent a vector as a matrix and transpose it?

c++

performance

transpose

vector

matrix