Есть ли более эффективный способ изменить размер двумерной сетки, представленной как Ve c<T>?

Question

У меня есть структура, содержащая двумерную сетку, представленную одним Vec<u8>, потому что wasm_bindgen не поддерживает <Vec<Vec<T>>. Например, сетка:

0 1 
2 3

хранится как Vec<u8> с элементами [0, 1, 2, 3] ( порядок старших строк ).

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

Чтобы установить ширину сетки, я разбиваю на Vec, превращая куски в векторы, изменяя размеры векторов и выравнивая векторы .

struct Matrix {
    grid: Vec<u8>,
    width: usize,
    height: usize,
}

impl Matrix {
    pub fn set_width(&mut self, new_width: usize) {
        self.grid = self
            .grid
            .chunks_exact(self.width)
            .flat_map(|chunk| {
                let mut chunk_vec = chunk.to_vec();
                chunk_vec.resize(new_width, 0);
                chunk_vec
            })
            .collect();

        self.width = new_width;
    }
}

Есть ли более эффективный способ сделать это? Я думаю, что блоки, вероятно, выделяют много памяти для больших размеров сетки, поскольку все они превращаются в Vec с.

---

Установка высоты намного проще, так как Vec потребуется только быть расширенным или усеченным:

pub fn set_height(&mut self, new_height: usize) {
    self.grid.resize(self.width * new_height, 0);
    self.height = new_height;
}

Answer 1

Чтобы просто уменьшить количество распределений, вы можете сделать закрытие переданным flat_map, возвращая итератор вместо Vec:

pub fn set_width(&mut self, new_width: usize) {
    use std::iter::repeat;
    self.grid = self
        .grid
        .chunks_exact(self.width)
        .flat_map(|chunk| chunk.iter().copied().chain(repeat(0)).take(new_width))
        .collect();

    self.width = new_width;
}

То есть для каждого чанка создайте итератор это возвращает copied содержимое чанка, за которым следует repeat ed строка 0, и усечение (take) до общего размера new_width. Для этого не требуется создавать Vec s для хранения промежуточных результатов, и поэтому он выделяет меньше ... скорее всего.

Это нормально, но могло бы быть и лучше. FlatMap не может знать размер внутренних итераторов, поэтому он не дает полезного size_hint (см. Эффективность выравнивания и сбора срезов для аналогичного примера). Это означает, что Vec в приведенном выше решении начинается пустым, и, возможно, его придется увеличить (перераспределить и скопировать его содержимое) несколько раз, прежде чем он станет достаточно большим. Вместо этого, мы можем сначала использовать Vec::with_capacity, чтобы зарезервировать правильное количество места, и extend вектор вместо collect ввода в него:

pub fn set_width(&mut self, new_width: usize) {
    use std::iter::repeat;
    let mut new_grid = Vec::with_capacity(self.grid.len() / self.width * new_width);
    for chunk in self.grid.chunks_exact(self.width) {
        new_grid.extend(chunk.iter().copied().chain(repeat(0)).take(new_width));
    }
    self.grid = new_grid;

    self.width = new_width;
}

Также можно изменить размер сетки в - место, с не более чем одним перераспределением (часто повторным использованием существующего). Однако этот алгоритм значительно сложнее. Выше я бы написал set_width, если только это не оказалось узким местом.

Answer 2

Сделал попытку изменить размер ширины сетки на месте, зарезервировав новую память только один раз, когда new_width> self.width:

use std::{cmp::Ordering, iter};

pub fn set_width(&mut self, new_width: usize) {
    match new_width.cmp(&self.width) {
        Ordering::Greater => {
            let width_diff = new_width - self.width;
            self.grid.reserve_exact(width_diff * self.height);

            for _ in 0..self.height {
                self.grid.extend(iter::repeat(0).take(width_diff));
                self.grid.rotate_right(new_width);
            }
        }

        Ordering::Less => {
            let width_diff = self.width - new_width;

            for _ in 0..self.height {
                self.grid.truncate(self.grid.len() - width_diff);
                self.grid.rotate_right(new_width);
            }
        }

        Ordering::Equal => (),
    }

    self.width = new_width;
}

Я думал об итерации по перевернутой Vec строки и использование splice для вставки / удаления значений, но я не уверен, что это более эффективно.

Использование splice:

use std::{cmp::Ordering, iter};

pub fn set_width(&mut self, new_width: usize) {
    match new_width.cmp(&self.width) {
        Ordering::Greater => {
            let width_diff = new_width - self.width;
            let width = self.width;
            self.grid.reserve_exact(width_diff * self.height);

            for i in (0..self.height).rev().map(|n| n * width + width) {
                self.grid.splice(i..i, iter::repeat(0).take(width_diff));
            }
        }

        Ordering::Less => {
            let width_diff = self.width - new_width;
            let width = self.width;
            for (start, end) in (1..=self.height)
                .rev()
                .map(|n| (n * width - width_diff, n * width))
            {
                self.grid.splice(start..end, iter::empty());
            }
        }

        Ordering::Equal => (),
    }

    self.width = new_width;
}

Answer 3

Актуален ли для вас порядок точек сетки? Если нет, я бы использовал другую сериализацию от 2D до 1D:

Если у вас есть такая матрица:

1 2 5
3 4 6
7 8 9

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

Вы можете сериализовать это в [1, 2, 3, 4, 5, 6, 7, 8, 9]

Предполагая все индексы и координаты начинаются с 0: если вы хотите получить доступ (n, m), вы найдете «слой», в котором находится значение матрицы, вычисляя max(n, m). N-й «слой» начнется с позиции индекса n * n. Внутри слоя вы найдете первые n элементы в части, добавленной справа, и следующие n+1 элементы в строке, добавленной внизу.