从后往前填充向量的最有效方法

Question

我正在尝试用一系列值填充一个向量。为了计算第一个值，我需要计算第二个值，它依赖于第三个值等等。

let mut bxs = Vec::with_capacity(n);

for x in info {
    let b = match bxs.last() {
        Some(bx) => union(&bx, &x.bbox),
        None => x.bbox.clone(),
    };
    bxs.push(b);
}
bxs.reverse();

目前我只是使用v.push(x)从前往后填充向量，然后使用v.reverse()反转该向量。是否有一种方法可以在单次遍历中完成此操作？

- Justin Raymond

---

这听起来非常适合使用递归。 - squiguy

“unsafe”的方式可能会更快，但我不确定它是否值得这样做。 - WiSaGaN

就我个人而言，我会按照你所描述的方式进行操作，先顺序推入，然后再反转。既然你肯定会进行一些分析以测试单次处理方案是否更有效率，那么你能否向我们展示这些分析结果，证明双次处理方案并不高效呢？ - Shepmaster

@Shepmaster 我认为你说得对，两次遍历更好。在代码的简洁性和性能之间做出权衡并不值得只进行一次遍历。 - Justin Raymond

虽然我不确定为什么两次遍历会比一次遍历更有效率。我能想到的唯一原因是方向会让预取器感到困惑，但是英特尔CPU可以检测到正向或反向内存访问流（https://dev59.com/gHI-5IYBdhLWcg3wPF12）。这个代码片段是光线追踪器的一部分，性能非常重要，对于大型图像，该代码段可能会运行数百万次。 - Justin Raymond

Answer 1

有没有一种方法可以一次性完成这个过程？

如果您不介意调整向量，那么就相对容易实现。

struct RevVec<T> {
    data: Vec<T>,
}

impl<T> RevVec<T> {
    fn push_front(&mut self, t: T) { self.data.push(t); }
}

impl<T> Index<usize> for RevVec<T> {
    type Output = T;
    fn index(&self, index: usize) -> &T {
        &self.data[self.len() - index - 1]
    }
}

impl<T> IndexMut<usize> for RevVec<T> {
    fn index_mut(&mut self, index: usize) -> &mut T {
        let len = self.len();
        &mut self.data[len - index - 1]
    }
}

- Matthieu M.

---

你的想法是把数据留在反向顺序中，但让访问从后往前工作吗？聪明。当你暴露这些情况时，你必须注意任何其他情况（迭代器等）。 - Shepmaster

@Shepmaster：是的，这就是想法，确实意味着反转所有访问。 - Matthieu M.

这个有没有相应的 crate 呢？它能够实现所有方法的反向操作（迭代等）。 - nirvana-msu

好的，找到了rev_slice这个库，其中实现了所有切片方法，尽管它是在一个新类型上实现的，所以不如它本可以更有用/通用。 - nirvana-msu

Answer 2

以下是使用unsafe的解决方案。相比使用reverse()的安全版本，不安全版本的速度略快2倍多。思路是使用Vec::with_capacity(usize)来分配向量，然后使用ptr::write(dst: *mut T, src: T)将元素从后往前写入向量中。offset(self, count: isize) -> *const T用于计算向量偏移量。

extern crate time;
use std::fmt::Debug;
use std::ptr;
use time::PreciseTime;

fn scanl<T, F>(u : &Vec<T>, f : F) -> Vec<T>
    where T : Clone,
          F : Fn(&T, &T) -> T {
    let mut v = Vec::with_capacity(u.len());

    for x in u.iter().rev() {
        let b = match v.last() {
            None => (*x).clone(),
            Some(y) => f(x, &y),
        };
        v.push(b);
    }
    v.reverse();
    return v;
}

fn unsafe_scanl<T, F>(u : &Vec<T> , f : F) -> Vec<T>
    where T : Clone + Debug,
          F : Fn(&T, &T) -> T {
    unsafe {
        let mut v : Vec<T> = Vec::with_capacity(u.len());

        let cap = v.capacity();
        let p = v.as_mut_ptr();

        match u.last() {
            None => return v,
            Some(x) => ptr::write(p.offset((u.len()-1) as isize), x.clone()),
        };
        for i in (0..u.len()-1).rev() {
            ptr::write(p.offset(i as isize), f(v.get_unchecked(i+1), u.get_unchecked(i)));
        }
        Vec::set_len(&mut v, cap);
        return v;
    }
}

pub fn bench_scanl() {
    let lo : u64 = 0;
    let hi : u64 = 1000000;
    let v : Vec<u64> = (lo..hi).collect();

    let start = PreciseTime::now();
    let u = scanl(&v, |x, y| x + y);
    let end= PreciseTime::now();
    println!("{:?}\n in {}", u.len(), start.to(end));

    let start2 = PreciseTime::now();
    let u = unsafe_scanl(&v, |x, y| x + y);
    let end2 = PreciseTime::now();
    println!("2){:?}\n in {}", u.len(), start2.to(end2));
}

- Justin Raymond

---

你可能不需要使用指针偏移量。此外，您的代码具有非典型的Rust特征，如对Vec :: set_len的UFCS调用，明确类型，&Vec而不是&[T]，比必要更宽的unsafe块，return语句，在类型中冒号前的空格等。您可能会想要在某个时候获得习惯性审查。 - Shepmaster

欢迎有更多经验的人改进解决方案。 - Justin Raymond

@JustinRaymond 你漏掉了几个 assert! / assert_eq! 调用。那段 unsafe 代码看起来对我来说不安全。 - wizzwizz4