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

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]);
}

此解决方案仅分配一次内存，其中包含容纳所有数字(包括双倍偶数)所需的确切空间。