vectoriteratorrust

Most efficient way to fill a vector from back to front


I am trying to populate a vector with a sequence of values. In order to calculate the first value I need to calculate the second value, which depends on the third value etc etc.

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();

Currently I just fill the vector front to back using v.push(x) and then reverse the vector using v.reverse(). Is there a way to do this in a single pass?


Solution

  • The solution using unsafe is below. The unsafe version is slightly more than 2x as fast as the safe version using reverse(). The idea is to use Vec::with_capacity(usize) to allocate the vector, then use ptr::write(dst: *mut T, src: T) to write the elements into the vector back to front. offset(self, count: isize) -> *const T is used to calculate the offset into the vector.

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