在C++中最快的矩阵转置方法是什么？

Question

在C++中最快的矩阵转置方法是什么？

93

我有一个（相对较大的）矩阵需要转置。例如，假设我的矩阵是

a b c d e f
g h i j k l
m n o p q r

我希望结果如下：

a g m
b h n
c I o
d j p
e k q
f l r

什么方法是最快的？

- mans

41

最快的方式不是旋转数组，而是在访问数组时仅仅交换索引顺序。 - High Performance Mark

2

无论多快，您都必须访问矩阵的所有元素。 - taocp

14

我猜这要看情况，如果你之后想要按行重复访问矩阵，有一个“转置”标志会对你造成很大影响。 - Matthieu M.

3

矩阵转置因其对内存缓存的影响而臭名昭著。如果您的数组足够大，以至于转置的性能非常重要，并且您无法通过提供具有交换索引的接口来避免转置，则最好的选择是使用现有的大型矩阵转置库例程。专家已经完成了这项工作，您应该使用它。 - Eric Postpischil

2

这个问题中有一些有用的信息（包括：使矩阵更大可以加快转置速度）。 - Eric Postpischil

显示剩余8条评论

12个回答

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

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

- Fayez Abdlrazaq Deab · Answer 1

我认为最快的方法不应该超过O(n^2)，而且这样你只能使用O(1)的空间：
做到这一点的方法是成对交换，因为当你转置一个矩阵时，你所做的是：M[i][j]=M[j][i]，所以将M[i][j]存储在temp中，然后M[i][j]=M[j][i]，最后一步：M[j][i]=temp。这可以通过一次遍历完成，所以它应该需要O(n^2)的时间复杂度。

- angel · Answer 2

我的答案是3x3矩阵的转置

 #include<iostream.h>

#include<math.h>


main()
{
int a[3][3];
int b[3];
cout<<"You must give us an array 3x3 and then we will give you Transposed it "<<endl;
for(int i=0;i<3;i++)
{
    for(int j=0;j<3;j++)
{
cout<<"Enter a["<<i<<"]["<<j<<"]: ";

cin>>a[i][j];

}

}
cout<<"Matrix you entered is :"<<endl;

 for (int e = 0 ; e < 3 ; e++ )

{
    for ( int f = 0 ; f < 3 ; f++ )

        cout << a[e][f] << "\t";


    cout << endl;

    }

 cout<<"\nTransposed of matrix you entered is :"<<endl;
 for (int c = 0 ; c < 3 ; c++ )
{
    for ( int d = 0 ; d < 3 ; d++ )
        cout << a[d][c] << "\t";

    cout << endl;
    }

return 0;
}