我正在制作矩阵乘法的施特拉森算法。该算法的基础是将矩阵 A (N * N) 分为四等分 A1-A4 (N/2 * N/2)。为此,我使用循环并为矩阵的每个四分之一分配内存。
int r;
double[,] A = new double[r, r];
double[,] A1 = new double[r / 2, r / 2];
double[,] A2 = new double[r / 2, r / 2];
double[,] A3 = new double[r / 2, r / 2];
double[,] A4 = new double[r / 2, r / 2];
for (int i = 0; i < r / 2; i++)
for (int j = 0; j < r / 2; j++)
{
A1[i, j] = A[i, j];
}
for (int i = 0; i < r / 2; i++)
for (int j = r / 2; j < r; j++)
{
A2[i, j - r / 2] = A[i, j];
}
for (int i = r / 2; i < r; i++)
for (int j = 0; j < r / 2; j++)
{
A3[i - r / 2, j] = A[i, j];
}
for (int i = r / 2; i < r; i++)
for (int j = r / 2; j < r; j++)
{
A4[i - r / 2, j - r / 2] = A[i, j];
}
有没有更简单的方法来做到这一点,而不需要额外的矩阵? (例如,A1=A [0 ... (n/2)-1, 0 ... (n/2)-1])?
最佳答案
我强烈建议使用所谓的 Morton order而不是此处矩阵的行优先或列优先布局内存布局。数据访问将变得更加容易(提供合适的索引计算功能)。此外,可以预先分配较小矩阵的空间,以便在每次递归调用中不需要分配和释放。请注意,对于每个较小的矩阵大小,仅需要使用一组矩阵,因为实际计算只让结果从较小的矩阵流向较大的矩阵。
参见here (3.3 数据布局)以获得更全面的解释。通常,类(class)中讲授Strassen算法时,不会提及合适的内存布局,这显然会导致永久地重新发现这种实现思想。
关于c# - 如何在不额外使用内存的情况下将矩阵分成四份?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23511312/