将一维矩阵数组转换为主一维矩阵的有趣算法挑战，需要有效的解决方案

Question

two typedefs

std::vector<double> Matrix;
std::vector<Matrix> MatrixBlocks;

矩阵

由一维向量表示，矩阵块表示矩阵向量。

问题是，给定矩阵块

包含来自具有特定排序的较大矩阵的子矩阵，我需要用矩阵块重建大矩阵。所以例如

假设大矩阵（存储为 std::vector<double> ）具有以下数据：

 1  2  3  4 
 5  6  7  8
 9  10 11 12
 13 14 15 16

下面包含上述矩阵的子矩阵的矩阵块具有以下数据：

索引 0：

1 2
5 6

索引 1：

3 4 
7 8 

索引 2：

9 10 
13 14 

索引 3：

11 12 
15 16

所以给定矩阵块我需要重建双精度的原始向量; 一维矩阵。有人有任何通用解决方案吗？

您可以假设，如果大矩阵始终是方形大小的矩阵。

编辑：

对于 NxN 矩阵，它被分解为 K mxm 矩阵，其中 N 可被 m 整除，您可以假设矩阵块的顺序如下：

索引 0：将包含从 [0，0] 到 （m，m） 的矩阵

索引 1：将包含从 [0，m] 到 （m， m + m） 的矩阵

索引 2：将包含从 [0，m+m] 到 （m， m + m + m） 的矩阵

。

直到最后一个索引将包含从 [m*i - m，m*i - m] 到 [m，m] 的矩阵

例如，如果主矩阵为 512x512

1 2 3 4 ... 512
513 ...   1014
 ...

261632（512*512-512） ...262144（512×512）

我们想拆分 512x512 矩阵 int 256 个 32x32 块，32 由用户选择，然后矩阵块将包含类似的东西

索引 0： 1 2 3 ...32 513 ...513 + 32 //..列长度为 32 的前 32 行

索引 1： 33 34 ...(33+32) (513+32+1) ...(513 + 32 + 1 + 32)//...同上

所以你可以看到它从索引 （0，0） 开始，从 （0，0） 到 （31，31） 提取第一个 32x32 元素;这是索引 0。 然后对于索引 1，起始位置为 （0，32），它从矩形 （0，32）、（0，63）、（31，32）、（31，63） 中提取数据

希望这是清楚的。所以上面 4x4 矩阵观察到的模式基本相同，对于任何矩阵大小都是相同的模式，唯一的区别是主矩阵并不总是大小为 4x4，我们将其拆分为的块大小并不总是 2x2。

Answer 1

这基本上归结为正确索引。

#include <cmath>
#include <iostream>
#include <vector>
int main()
{
  std::vector<double> v(16);
  std::vector<std::vector<double> > m;
  std::vector<double> m1 {1,2,5,6};
  m.push_back(m1);
  std::vector<double> m2 {3,4,7,8};
  m.push_back(m2);
  std::vector<double> m3 {9,10,13,14};
  m.push_back(m3);
  std::vector<double> m4 {11,12,15,16};
  m.push_back(m4);
  size_t idx = 0;
  for (size_t big_row = 0; big_row < std::sqrt(m.size()); ++big_row)
  for (size_t small_row = 0; small_row < std::sqrt(m1.size()); ++small_row)
  for (size_t big_col = 0; big_col < std::sqrt(m.size()); ++big_col)
  for (size_t small_col = 0; small_col < std::sqrt(m1.size()); ++small_col)
  {
    v[idx] = m[big_col + std::sqrt(m.size()) * big_row][small_col + std::sqrt(m1.size()) * small_row];
    ++idx;
  }
  for (unsigned i = 0; i < 16; ++i)
    std::cout << v[i] << std::endl;
}

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Answer 2

假设原始矩阵是大 NxN，每个子矩阵都是 nxn。一侧的子矩阵数为 （N/n）;让我们称之为K。

我们可以把大矩阵想象成一个很长的、n*k*n*k长度的列表。

我们可以将大矩阵索引映射到子矩阵数和索引，反之亦然。正向映射似乎非常复杂，我只是通过首先写出我想要的子矩阵索引作为一个序列，然后编写一个函数来生成该序列（当然还有时间测试试错法）。

一些演示第一种方法的代码（请原谅灰尘）：

#include <iostream>
#include <vector>
int main() {
  // Initialize the Vector and Set up the Matrices
  std::vector<double> v(36);
  std::vector<std::vector<double> > m;
  std::vector<double> m1 {1,2,7,8};
  m.push_back(m1);
  std::vector<double> m2 {3,4,9,10};
  m.push_back(m2);
  std::vector<double> m3 {5,6,11,12};
  m.push_back(m3);
  std::vector<double> m4 {13,14,19,20};
  m.push_back(m4);
  std::vector<double> m5 {15,16,21,22};
  m.push_back(m5);
  std::vector<double> m6 {17,18,23,24};
  m.push_back(m6);
  std::vector<double> m7 {25,26,31,32};
  m.push_back(m7);
  std::vector<double> m8 {27,28,33,34};
  m.push_back(m8);
  std::vector<double> m9 {29,30,35,36};
  m.push_back(m9);
  // These variables (see explanation above) take on these values for this example
  unsigned N = 6;
  unsigned n = 2;
  unsigned k = N/n;
  // Constructing the Big Matrix    
  for (unsigned i = 0; i < N*N; ++i) {
    int a = (i / (n * k * n)) * k + ((i / n) % k);
    int b = (i % (n * k * n)) % n + ((i % (n * k * n)) / (n * k) * n);
    v[i] = m[a][b];
    std::cout << a << "t" << b << "t" << v[i] << std::endl;
  }
}

我们还可以通过遍历子矩阵列表并将每个索引映射回大矩阵来处理反向映射。我还没有编码，但你明白了。

无论哪种方式，算法在所有情况下都应该花费 O（N^2） 时间（N 是大矩阵的一侧）。如果你让 N 是矩阵的大小，那么它是线性时间。

这对您的应用程序来说是否足够高效？