是否有更有效的方法来调整表示为Vec<T>

Question

因为wasm_bindgen不支持<Vec<Vec<T>>，所以我有一个包含由单个Vec<u8>表示的二维网格的结构。例如，网格：

0 1 
2 3

被存储为具有元素CCD_ 5的CCD_。

我希望能够调整网格的宽度；如果新宽度较小，则网格应从右侧删除列；如果新宽度较大，则网格应使用零填充新列。可能必须在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;
}
}

有没有更有效的方法可以做到这一点？我认为区块可能在大网格上分配了大量内存，因为它们都变成了Vecs。

---

设置高度要容易得多，因为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内容，后跟0的repeated字符串，并将其截断(take(为总大小new_width。这不需要创建任何Vec来存储中间结果，因此它分配的。。。很可能。

这还可以，但可能会更好。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

网格点的顺序与您相关吗？如果没有，我会使用从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元素。

Answer 3

尝试调整网格宽度，仅在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;
}