C++如何将向量表示为矩阵并对其进行转置？

Question

C++如何将向量表示为矩阵并对其进行转置？

3

我有一个大小为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都没有关系

- user1209304

3

“我需要找到R和C。”- 在您提供的案例或一般情况下，没有足够的信息可以推导出R和C，在您的案例中，R可以是4或2，而C可以是2或4。 - Pixelchemist

2

@igor，不可能是3x3！OP说n是2的幂，而且4x2或2x4也永远不会是3x3。 - Khalil Khalaf

1

@Igor：2x4 == 4x2 == 8 != 3x3 == 9 - Pixelchemist

1

@user1209304 2x4 转置展平产生的结果将与 4x2 转置展平产生的结果不同。 - callyalater

无论如何，我真的无法弄清楚你想做什么。也许Eigen可以帮助你，它可以转置东西并且可以接口C样式数组。 - Baum mit Augen

显示剩余12条评论

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- revainisdead · 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]

等等。

- polfosol ఠ_ఠ · 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);
        }
    }
}

请查看实时示例

- Carafini · 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 是“转置”的平坦向量，R 和 C 分别是您找到的矩阵表示的行和列向量。