如何将1D矩阵阵列中的元素重新排列到位

Question

我想对齐表示为一维数组的5x5矩阵的内存。

原始数组如下所示：

let mut a = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25];

或

[ 1  2  3  4  5  ]
[ 6  7  8  9  10 ]
a = [ 11 12 13 14 15 ]
[ 16 17 18 19 20 ]
[ 21 22 23 24 25 ]

具有25个元件的长度。

将内存大小调整到内存对齐的边界(2的幂(后，数组将如下所示：

a = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ];

或

[ 1  2  3  4  5  6  7  8  ]
[ 9  10 11 12 13 14 15 16 ]
[ 17 18 19 20 21 22 23 24 ]
[ 25 0  0  0  0  0  0  0  ]
a = [ 0  0  0  0  0  0  0  0  ]
[ 0  0  0  0  0  0  0  0  ]
[ 0  0  0  0  0  0  0  0  ]
[ 0  0  0  0  0  0  0  0  ] 

a的len现在是64个元素。

因此它将成为8x8矩阵

目标是具有以下表示形式：

a = [1 2 3 4 5 0 0 0 6 7 8 9 10 0 0 0 11 12 13 14 15 0 0 0 16 17 18 19 20 0 0 0 21 22 23 24 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ];

或

[ 1  2  3  4  5  0 0 0 ]
[ 6  7  8  9  10 0 0 0 ]
[ 11 12 13 14 15 0 0 0 ]
[ 16 17 18 19 20 0 0 0 ]
[ 21 22 23 24 25 0 0 0 ]
[ 0  0  0  0  0  0 0 0 ]
[ 0  0  0  0  0  0 0 0 ]
[ 0  0  0  0  0  0 0 0 ]

背景是将a内存对齐为2的幂，因此可以部分并行进行计算(对于OpenCLfloat4，或可用的向量大小。(。我也不想使用新数组简单地将旧元素插入正确的位置，以保持低内存消耗。

起初，我考虑交换范围内的元素，在这个范围内，数组末尾的元素应该有一个零，保持一个指向元素的指针并模拟一个队列，但元素会在末尾堆积起来，我没有想出一个有效的解决方案。

我选择的语言是铁锈。有什么聪明的算法可以达到预期的结果吗？

Answer 1

因此，您有一个N*N矩阵，表示为大小为N^2的向量，然后将向量调整为M^2(M>N(，使前N^2个元素为原始元素。现在要重新排列原始元素，使M*M矩阵左上角的N*N子矩阵与原始元素相同。

• 需要注意的一件事是，如果向后走，则永远不会覆盖以后需要的值。

• 索引X在M*M矩阵中的位置是行X/M(整数除法(和列X%M。

• 索引X的所需位置是行X/N和列X%N

• M*M矩阵中的行R和列C处的元素具有索引R*M+C

现在，根据所有这些信息，我们可以得出公式，为旧索引X获得新索引Y：

Y = (X / N) * M + (X % N)

因此，您可以从N^2-1到N进行循环，然后将元素复制到使用公式计算的新位置，并将其原始位置设置为0。(所有东西都是基于0的，我希望rust也是基于0，否则你将不得不添加一些+1。(

Answer 2

根据maraca的解决方案，代码如下所示：

fn zeropad<T: Copy>(
first: T,
data: &mut Vec<T>,
dims: (usize, usize),
) -> (usize, usize) {
let r = next_pow2(dims.0);
let c = next_pow2(dims.1);
if (r, c) == (dims.0, dims.1) {
return (r, c);
}
let new_len = r * c;
let old_len = data.len();
let old_col = dims.1;
// resize
data.resize(new_len, first);
for i in (old_col..old_len).rev() {
let row: usize = i / c;
let col: usize = i % c;
// bigger matrix
let pos_old = row * c + col;
// smaller matrix
let pos_new = (i / dims.1) * c + (i % dims.1);
data[pos_new] = data[pos_old];
data[pos_old] = first;
}
return (r, c);
}