如何根据条件重复向量中的某些元素？

Question

我在 kata 期间遇到了这个问题。我更具可读性的实现如下：

use std::vec::Vec;

fn repeat_even(v: Vec<i32>) -> Vec<i32> {
    v.into_iter().flat_map(|x| match x % 2 { 0 => vec![x, x], _ => vec![x] }).collect()
}

fn main() {
    let v = vec![1, 2, 3, 4, 6];
    assert_eq!(repeat_even(v), vec![1, 2, 2, 3, 4, 4, 6, 6]);
}

我有两个问题：

是否有必要再创建一个Vec？是否可以使用相同的 Vec，即在迭代时修改它？
我想我的解决方案是低效的：我分配了很多向量，但我不能保证这会得到优化。有没有更好的解决方案：可读且分配更少？

Answer 1

您可以在同一个向量中执行此操作，但每次遇到偶数时都需要移动向量的其余部分（在翻倍后），这是低效的。最好使用一个新的向量和一个简单的循环来完成：

fn main() {
    let v = vec![1, 2, 3, 4, 6];

    let mut v2 = Vec::with_capacity(v.len() + v.iter().filter(|&n| n % 2 == 0).count());

    for n in v {
        v2.push(n);
        if n % 2 == 0 { v2.push(n) }
    }

    assert_eq!(v2, vec![1, 2, 2, 3, 4, 4, 6, 6]);
}

此解决方案只分配一次内存，精确 space 需要保存所有数字，包括双倍偶数。

Answer 2

Is it necessary to create another Vec? Is is possible to use the same Vec, i.e. modify it while iterating?

可能但效率不高。 Vec 在堆上分配一块内存，其中每个元素都与下一个元素相邻。如果您只想对每个元素执行一些数字运算，那么可以，您可以就地执行该操作。但是您需要在其他元素之间插入新元素 ，这意味着将所有以下元素向右移动一个位置并（可能）分配更多内存。

您正在考虑的 Haskell 代码可能使用了 Haskell Data.List，它是一个链表而不是向量。如果您使用像 Data.Vector.Unboxed or repa 这样更节省内存的结构，那么您也将无法在迭代时插入元素。

My solution is, as I imagine, inefficient: I allocate a lot of vectors, and I have no guarantee that this will be optimized. Is it a better solution: readable and with less allocation?

这样的事情可能会奏效。它仍然具有功能性感觉，但通过分配一个 Vec 然后对其进行变异来工作：

fn double_even(v: Vec<i32>) -> Vec<i32> { // allocate for the worst case (i.e. all elements of v are even) let result = Vec::with_capacity(v.len() * 2); v.into_iter().fold(result, |mut acc, n| { acc.push(n); if n % 2 == 0 { acc.push(n); } acc }) }

你也可以在最后 shrink_to_fit()，但它看起来有点难看，因为你不能 return 解决方案作为表达式。

Answer 3

flat_map 需要迭代器，因此您可以 return 值的迭代器：

use std::iter;

fn double_even(v: &[i32]) -> Vec<i32> {
    v.iter().flat_map(|&x| {
        let count = if x % 2 == 0 { 2 } else { 1 };
        iter::repeat(x).take(count)
    }).collect()
}

fn main() {
    let v = vec![1, 2, 3, 4, 6];
    assert_eq!(double_even(&v), vec![1, 2, 2, 3, 4, 4, 6, 6]);
}

注意事项：

没有理由 use std::vec::Vec。它已经通过 prelude.
您没有使用传入向量的内存分配，因此没有理由接受它。另见
不要使用vec!()；使用 vec![] 代替。这对编译器无关紧要，但对人类很重要。

如果您真的打算尝试重用内存，我会向后沿着迭代器走，以帮助避免索引失效:

fn double_even(mut v: Vec<i32>) -> Vec<i32> {
    for i in (0..v.len()).rev() {
        let val = v[i]; 
        if val % 2 == 0 {
            v.insert(i, val);
        }
    }
    v
}

这在算法上可能更糟；每个 insert 移动它后面的所有数据。我相信最坏的情况是 O(n^2) 当每个元素都是偶数时。

我通常也不会在这里按值计算。相反，我会采用可变引用。如果你真的需要它，你总是可以把它换回一个值：

fn double_even_ref(v: &mut Vec<i32>) {
    for i in (0..v.len()).rev() {
        let val = v[i];
        if val % 2 == 0 {
            v.insert(i, val);
        }
    }
}

fn double_even(mut v: Vec<i32>) -> Vec<i32> {
    double_even_ref(&mut v);
    v
}

Answer 4

Is it necessary to create another Vec? Is is possible to use the same Vec, i.e. modify it while iterating?

My solution is, I imagine, inefficient: I allocate a lot of vectors, and I have no guarantee that this will be optimized. Is there a better solution: readable and with less allocation?

你可以做的一件非常惯用的事情是将你的函数实现为一个“迭代器适配器”——也就是说，而不是特别处理 Vec，看看 Iterators of i32 元素代替。然后一切都将成为堆栈上的变量，根本不会进行任何分配。它可能看起来像这样：

struct DoubleEven<I> {
    iter: I,
    next: Option<i32>,
}

impl<I> Iterator for DoubleEven<I>
    where I: Iterator<Item=i32>
{
    type Item = i32;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().or_else(||
            self.iter.next().map(|value| {
                if value % 2 == 0 { self.next = Some(value) }
                value
            })
        )
    }
}

那你可以写

fn main() {
    let vec = vec![1, 2, 3, 4, 5, 6];
    let double_even = DoubleEven {
        iter: vec.into_iter(),
        next: None,
    };
    for x in double_even {
        print!("{}, ", x)  // prints 1, 2, 2, 3, 4, 4, 5, 6, 6, 
    }
}

更好的是，您可以将函数 double_even 添加到任何可以变成 i32 的迭代器的对象，从而允许您编写以下内容：

trait DoubleEvenExt : IntoIterator + Sized {
    fn double_even(self) -> DoubleEven<Self::IntoIter> {
        DoubleEven {
            iter: self.into_iter(),
            next: None,
        }
    }
}

impl<I> DoubleEvenExt for I where I: IntoIterator<Item=i32> {}

fn main() {
    let vec = vec![1, 2, 3, 4, 5, 6];
    for x in vec.double_even() {
        print!("{}, ", x)  // prints 1, 2, 2, 3, 4, 4, 5, 6, 6, 
    }
}

现在我承认，在这种情况下，样板文件正在增加，但您可以在调用站点看到代码确实非常简洁。对于更复杂的适配器，此模式可能非常有用。此外，除了最初的 Vec 分配之外，还有 no 内存分配正在进行！只是堆栈分配的变量，允许在发布版本中使用高效代码。

如何根据条件重复向量中的某些元素？

How do I repeat some elements in a vector based on a condition?

performance

vector

mutability

rust