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

Question

两个类型定义

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

Matrix 由一维 vector 表示，MatrixBlocks 表示矩阵的 vector 。

问题是，鉴于矩阵 block 包含来自具有特定顺序的较大矩阵的子矩阵，我需要用矩阵 block 重建大矩阵。例如

假设大矩阵(存储为std::vector<double>)有以下数据:

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

下面包含上述矩阵的子矩阵的 MatrixBlocks 具有以下数据:

索引 0:

1 2
5 6

索引 1:

3 4 
7 8 

索引 2:

9 10 
13 14 

索引 3:

11 12 
15 16

所以鉴于 MatrixBlock 我需要重建 double 的原始 vector ；一维矩阵。有人有任何通用的解决方案吗？

你可以假设如果大矩阵总是一个正方形大小的矩阵。

编辑:

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

索引 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 矩阵拆分为 256 个 32x32 block ，用户选择 32，然后 MatrixBlock 将包含类似的内容

索引 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，我们将其拆分成的 block 大小也不总是 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