Как переставить элементы в одномерном матричном массиве на месте?

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  ] 

длина элемента теперь составляет 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 память, выровненную по степени двойки, поэтому вычисления могут частично выполняться параллельно (для OpenCL float4 или для доступных векторных размеров.). Я также не хочу использовать новый массив, чтобы просто вставить старые элементы в правильные позиции, чтобы сохранить низкое потребление памяти.

Сначала я думал об обмене элементами в диапазоне, где должен быть ноль с элементами в конце массива, сохраняя указатель на элементы и моделируя очередь, но элементы будут складываться до конца, и я не придумал рабочего решения.

Мой язык выбора - ржавчина. Есть ли какой-нибудь умный алгоритм для достижения желаемого результата?

Answer 1

Итак, у вас есть матрица N * N, представленная в виде вектора размером N ^ 2, затем вы изменяете размер вектора до M ^ 2 (M> N), так что первые N ^ 2 элемента являются исходными. Теперь вы хотите изменить порядок исходных элементов, чтобы подматрица N * N в верхнем левом углу матрицы M * M была такой же, как и исходная.

• обратите внимание, что если вы go задом наперед, вы никогда не перезапишете значение, которое вам понадобится позже.

• Позиция индекса X в матрице M * M - строка X / M ( целочисленное деление) и столбец X% M.

• Желаемая позиция индекса X - строка X / N и столбец X% N

• An элемент в строке R и столбце C в матрице M * M имеет индекс R * M + C

Теперь, взяв всю эту информацию, мы можем придумать формулу для получить новый индекс Y для старого индекса X:

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

Таким образом, вы можете просто сделать al oop из N ^ 2 - 1 в N и скопировать элемент в новую позицию, рассчитанную по формуле и установите его исходное положение на 0. (Все основано на 0, я надеюсь, что ржавчина тоже на 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);
}