如何将一些矩阵合并为一个？
How to combine some matrix into one?
我正在尝试使用分治法进行矩阵乘法。所以，我认为，我已经将分解部分分解为子问题（递归情况和基本情况）。
因此，我有四个象限（左上、左下、右上、右下），我正在考虑如何将它们组合成一个结果矩阵，但我没有主意。
我正在使用 Java，所以我有 matrixA 和 matrixB，还有一些索引，例如 matrixRowsA、matrixColumnsA、matrixRowsB、matrixColumnsB
通过这种方式，我避免创建新矩阵和所有只会使问题解决成本更高的东西。
所以基本问题是，如何将 4 个子矩阵连接成一个填充子矩阵？
所以方法是调用 divideAndConquer:
private static int[][] divideAndConquer(int[][]matrixA, int beginRowsA, int endRowsA, int beginColumnsA,
int endColumnsA, int[][]matrixB, int beginRowsB, int endRowsB,
int beginColumnsB, int endColumnsB)
{
// Base case
if(lengthOfBothMatrix()==1)
{
return multiplyMatrix(matrixA,matrixB);
}
}
else
{
int middleRowsA = obtainMiddleRowsB();
int middleColumnsA = obtainMiddleColumnsA();
int middleRowsB = obtainMiddleRowsB();
int middleColumnsB = obtainMiddleColumnsB();
int[][] leftSuperiorQuadrant = matrixAddition(divideAndConquer(matrixA, beginRowsA, middleRowsA, beginColumnsA, middleColumnsA, matrixB, beginRowsB,
middleRowsB, beginColumnsB, middleColumnsB),
divideAndConquer(matrixA, beginRowsA, middleRowsA, middleColumnsA+1, endColumnsA,
matrixB, middleRowsB+1, endRowsB, beginColumnsB, middleColumnsB));
int[][] leftInferiorQuadrant = matrixAddition(divideAndConquer(matrixA, middleRowsA+1, endRowsA, beginColumnsA, middleColumnsA,
matrixB, beginRowsB,middleRowsB, beginColumnsB, middleColumnsB),
divideAndConquer(matrixA, middleRowsA+1, endRowsA, middleColumnsA+1, endColumnsA,
matrixB, middleRowsB+1, endRowsB, beginColumnsB, middleColumnsB));
int[][] rightSuperiorQuadrant = matrixAddition(divideAndConquer(matrixA, beginRowsA, middleRowsA, beginColumnsA, middleColumnsA,
matrixB, beginRowsB, middleRowsB, middleColumnsB+1, endColumnsB),
divideAndConquer(matrixA, beginRowsA, middleRowsA, middleColumnsA+1, endColumnsA,
matrixB, middleRowsB+1, endRowsB, middleColumnsB+1, endColumnsB));
int[][] rightInferiorQuadrant =matrixAddition(divideAndConquer(matrixA, middleRowsA+1, endRowsA, beginColumnsA, middleColumnsA,
matrixB, beginRowsB, middleRowsB, middleColumnsB+1, endColumnsB),
divideAndConquer(matrixA, middleRowsA+1, endRowsA, middleColumnsA+1, endColumnsA,
matrixB, middleRowsB+1, endRowsB, middleColumnsB+1, endColumnsB));
我正在测试两个矩阵，例如：
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
首先，您可以将左矩阵 (leftSuperiorQuadrant & leftInferiorQuadrant) 和右矩阵 (rightSuperiorQuadrant & rightInferiorQuadrant) 垂直连接到一个新的列矩阵 System.arraycopy():
int leftSuperiorQuadrant [][] = {{1, 2}, {3, 4}};
int rightSuperiorQuadrant [][] = {{5, 6}, {7, 8}};
int leftInferiorQuadrant [][] = {{9, 10}, {11, 12}};
int rightInferiorQuadrant [][] = {{13, 14}, {15, 16}};
int m_intermediate_left[][] = new int[leftSuperiorQuadrant.length+leftInferiorQuadrant.length][];
int m_intermediate_right[][] = new int[rightSuperiorQuadrant.length+rightInferiorQuadrant.length][];
// Concat leftSuperiorQuadrant and leftInferiorQuadrant in column
System.arraycopy(leftSuperiorQuadrant, 0, m_intermediate_left, 0, leftSuperiorQuadrant.length);
System.arraycopy(leftInferiorQuadrant, 0, m_intermediate_left, leftSuperiorQuadrant.length, leftInferiorQuadrant.length);
// Concat rightSuperiorQuadrant and rightInferiorQuadrant in column
System.arraycopy(rightSuperiorQuadrant, 0, m_intermediate_right, 0, rightSuperiorQuadrant.length);
System.arraycopy(rightInferiorQuadrant, 0, m_intermediate_right, rightSuperiorQuadrant.length, rightInferiorQuadrant.length);
System.out.println(Arrays.deepToString(m_intermediate_left));
System.out.println(Arrays.deepToString(m_intermediate_right));
这个returns:
[[1, 2], [3, 4], [9, 10], [11, 12]]
1 | 2
3 | 4
9 | 10
11 | 12
[[5, 6], [7, 8], [13, 14], [15, 16]]
5 | 6
7 | 8
13 | 14
15 | 16
然后，您可以手动水平连接这些结果矩阵：
int m_final[][] = new int[m_intermediate_left.length][m_intermediate_left[0].length+m_intermediate_right[0].length];
// For each row of the final matrix
for(int i = 0; i < m_final.length; i++) {
// For each column of the final matrix
for (int j = 0; j < m_final[0].length; j++) {
// If j corresponds to the left columns, add left matrix values
if (j < m_intermediate_left[0].length) {
m_final[i][j] = m_intermediate_left[i][j];
}
// If j corresponds to the right columns, add the right matrix values
else {
m_final[i][j] = m_intermediate_right[i][j - m_intermediate_left[0].length];
}
}
}
System.out.println(Arrays.deepToString(m_final));
这个returns你的欲望矩阵：
[[1, 2, 5, 6], [3, 4, 7, 8], [9, 10, 13, 14], [11, 12, 15, 16]]
1 | 2 | 5 | 6
3 | 4 | 7 | 8
9 | 10 | 13 | 14
11 | 12 | 15 | 16
请注意，如果您的象限大小不同，它将不起作用。
最佳
我还想要：
- 要指出的是，分而治之中的除法应该沿着（乘法）算法的"break"线;
- 提一下不错Arraysclass.
做一个明智的除法，即使是最懒惰的努力，也很重要。
对于矩阵乘法，分成两半似乎更合适：
非常粗略：
A: (3x5) B: (5x3) A x B: (3x3)
a a b b b c c c ... ac ... bd ...
a a b b b c c c
a a b b b d d d
d d d
d d d
如您所见，您可以将任务拆分为 Aa x Bc 和 Ab x Bd，然后干净利落地合并结果。
这个够复杂了，也很容易理解。
另一个技巧是使用更数学化的简短 名称以便于阅读。虽然通常应该使用足够长的名称，但课程可能要求相反。
int[][] multiply(int[][] a, int[][] b) {
int rows = a.length;
int cols = b[0].length;
int terms = b.length:
if (terms != a[0].length) {
throw new IllegalArgumentException(
"Dimensions do not match: " + a[0].length + " != " + terms);
}
int[][] product = new int[rows][cols];
if (terms < 2) { // Cannot divide
if (terms == 1) {
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
product[i][j] = a[i][0] * b[0][j];
}
}
}
} else {
int half = terms/2;
int[][] aLeft = new int[rows][half];
int[][] bTop = new int[half][cols];
... fill using Arrays.copyOfRange ...
int[][] prodLT = multiply(aLeft, bTop);
int[][] aRight = new int[rows][terms - half];
int[][] bBottom = new int[terms - half][cols];
... fill using Arrays.copyOfRange ...
int[][] prodRB = multiply(aRight, bBottom);
... add prodLT to prodRB into product
}
return product;
}
我正在尝试使用分治法进行矩阵乘法。所以，我认为，我已经将分解部分分解为子问题（递归情况和基本情况）。
因此，我有四个象限（左上、左下、右上、右下），我正在考虑如何将它们组合成一个结果矩阵，但我没有主意。
我正在使用 Java，所以我有 matrixA 和 matrixB，还有一些索引，例如 matrixRowsA、matrixColumnsA、matrixRowsB、matrixColumnsB
通过这种方式，我避免创建新矩阵和所有只会使问题解决成本更高的东西。
所以基本问题是，如何将 4 个子矩阵连接成一个填充子矩阵？
所以方法是调用 divideAndConquer:
private static int[][] divideAndConquer(int[][]matrixA, int beginRowsA, int endRowsA, int beginColumnsA,
int endColumnsA, int[][]matrixB, int beginRowsB, int endRowsB,
int beginColumnsB, int endColumnsB)
{
// Base case
if(lengthOfBothMatrix()==1)
{
return multiplyMatrix(matrixA,matrixB);
}
}
else
{
int middleRowsA = obtainMiddleRowsB();
int middleColumnsA = obtainMiddleColumnsA();
int middleRowsB = obtainMiddleRowsB();
int middleColumnsB = obtainMiddleColumnsB();
int[][] leftSuperiorQuadrant = matrixAddition(divideAndConquer(matrixA, beginRowsA, middleRowsA, beginColumnsA, middleColumnsA, matrixB, beginRowsB,
middleRowsB, beginColumnsB, middleColumnsB),
divideAndConquer(matrixA, beginRowsA, middleRowsA, middleColumnsA+1, endColumnsA,
matrixB, middleRowsB+1, endRowsB, beginColumnsB, middleColumnsB));
int[][] leftInferiorQuadrant = matrixAddition(divideAndConquer(matrixA, middleRowsA+1, endRowsA, beginColumnsA, middleColumnsA,
matrixB, beginRowsB,middleRowsB, beginColumnsB, middleColumnsB),
divideAndConquer(matrixA, middleRowsA+1, endRowsA, middleColumnsA+1, endColumnsA,
matrixB, middleRowsB+1, endRowsB, beginColumnsB, middleColumnsB));
int[][] rightSuperiorQuadrant = matrixAddition(divideAndConquer(matrixA, beginRowsA, middleRowsA, beginColumnsA, middleColumnsA,
matrixB, beginRowsB, middleRowsB, middleColumnsB+1, endColumnsB),
divideAndConquer(matrixA, beginRowsA, middleRowsA, middleColumnsA+1, endColumnsA,
matrixB, middleRowsB+1, endRowsB, middleColumnsB+1, endColumnsB));
int[][] rightInferiorQuadrant =matrixAddition(divideAndConquer(matrixA, middleRowsA+1, endRowsA, beginColumnsA, middleColumnsA,
matrixB, beginRowsB, middleRowsB, middleColumnsB+1, endColumnsB),
divideAndConquer(matrixA, middleRowsA+1, endRowsA, middleColumnsA+1, endColumnsA,
matrixB, middleRowsB+1, endRowsB, middleColumnsB+1, endColumnsB));
我正在测试两个矩阵，例如：
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
首先，您可以将左矩阵 (leftSuperiorQuadrant & leftInferiorQuadrant) 和右矩阵 (rightSuperiorQuadrant & rightInferiorQuadrant) 垂直连接到一个新的列矩阵 System.arraycopy():
int leftSuperiorQuadrant [][] = {{1, 2}, {3, 4}};
int rightSuperiorQuadrant [][] = {{5, 6}, {7, 8}};
int leftInferiorQuadrant [][] = {{9, 10}, {11, 12}};
int rightInferiorQuadrant [][] = {{13, 14}, {15, 16}};
int m_intermediate_left[][] = new int[leftSuperiorQuadrant.length+leftInferiorQuadrant.length][];
int m_intermediate_right[][] = new int[rightSuperiorQuadrant.length+rightInferiorQuadrant.length][];
// Concat leftSuperiorQuadrant and leftInferiorQuadrant in column
System.arraycopy(leftSuperiorQuadrant, 0, m_intermediate_left, 0, leftSuperiorQuadrant.length);
System.arraycopy(leftInferiorQuadrant, 0, m_intermediate_left, leftSuperiorQuadrant.length, leftInferiorQuadrant.length);
// Concat rightSuperiorQuadrant and rightInferiorQuadrant in column
System.arraycopy(rightSuperiorQuadrant, 0, m_intermediate_right, 0, rightSuperiorQuadrant.length);
System.arraycopy(rightInferiorQuadrant, 0, m_intermediate_right, rightSuperiorQuadrant.length, rightInferiorQuadrant.length);
System.out.println(Arrays.deepToString(m_intermediate_left));
System.out.println(Arrays.deepToString(m_intermediate_right));
这个returns:
[[1, 2], [3, 4], [9, 10], [11, 12]]
1 | 2
3 | 4
9 | 10
11 | 12
[[5, 6], [7, 8], [13, 14], [15, 16]]
5 | 6
7 | 8
13 | 14
15 | 16
然后，您可以手动水平连接这些结果矩阵：
int m_final[][] = new int[m_intermediate_left.length][m_intermediate_left[0].length+m_intermediate_right[0].length];
// For each row of the final matrix
for(int i = 0; i < m_final.length; i++) {
// For each column of the final matrix
for (int j = 0; j < m_final[0].length; j++) {
// If j corresponds to the left columns, add left matrix values
if (j < m_intermediate_left[0].length) {
m_final[i][j] = m_intermediate_left[i][j];
}
// If j corresponds to the right columns, add the right matrix values
else {
m_final[i][j] = m_intermediate_right[i][j - m_intermediate_left[0].length];
}
}
}
System.out.println(Arrays.deepToString(m_final));
这个returns你的欲望矩阵：
[[1, 2, 5, 6], [3, 4, 7, 8], [9, 10, 13, 14], [11, 12, 15, 16]]
1 | 2 | 5 | 6
3 | 4 | 7 | 8
9 | 10 | 13 | 14
11 | 12 | 15 | 16
请注意，如果您的象限大小不同，它将不起作用。
最佳
我还想要：
- 要指出的是，分而治之中的除法应该沿着（乘法）算法的"break"线;
- 提一下不错Arraysclass.
做一个明智的除法，即使是最懒惰的努力，也很重要。 对于矩阵乘法，分成两半似乎更合适：
非常粗略：
A: (3x5) B: (5x3) A x B: (3x3)
a a b b b c c c ... ac ... bd ...
a a b b b c c c
a a b b b d d d
d d d
d d d
如您所见，您可以将任务拆分为 Aa x Bc 和 Ab x Bd，然后干净利落地合并结果。
这个够复杂了，也很容易理解。
另一个技巧是使用更数学化的简短 名称以便于阅读。虽然通常应该使用足够长的名称，但课程可能要求相反。
int[][] multiply(int[][] a, int[][] b) {
int rows = a.length;
int cols = b[0].length;
int terms = b.length:
if (terms != a[0].length) {
throw new IllegalArgumentException(
"Dimensions do not match: " + a[0].length + " != " + terms);
}
int[][] product = new int[rows][cols];
if (terms < 2) { // Cannot divide
if (terms == 1) {
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
product[i][j] = a[i][0] * b[0][j];
}
}
}
} else {
int half = terms/2;
int[][] aLeft = new int[rows][half];
int[][] bTop = new int[half][cols];
... fill using Arrays.copyOfRange ...
int[][] prodLT = multiply(aLeft, bTop);
int[][] aRight = new int[rows][terms - half];
int[][] bBottom = new int[terms - half][cols];
... fill using Arrays.copyOfRange ...
int[][] prodRB = multiply(aRight, bBottom);
... add prodLT to prodRB into product
}
return product;
}