algorithm - 如何在原位重新排列一维矩阵阵列中的元素？

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的幂，因此可以并行进行部分计算(对于OpenCL float4或可用的矢量大小)。我也不想使用新的数组来简单地将旧元素插入正确的位置，以保持较低的内存消耗。

最初，我考虑过要交换该范围内的元素，该范围的元素应在数组的末尾为零，保持指向这些元素的指针并模拟一个队列，但是元素会朝末尾堆叠，我没有想出可行的解决方案。

我选择的语言是使用rust 。是否有任何智能算法可以达到预期效果？

Answer 1

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

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

M * M矩阵中索引X的位置是行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。好，否则您将不得不添加+1。)