从后到前填充向量的最有效方法 [英] 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();
当前,我只是使用v.push(x)
从前向后填充向量,然后使用v.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?
推荐答案
使用unsafe
的解决方案如下.不安全版本的速度是使用reverse()
的安全版本的两倍多.这个想法是使用Vec::with_capacity(usize)
分配向量,然后使用 offset(self, count: isize) -> *const T
用于计算向量中的偏移量.>
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));
}
这篇关于从后到前填充向量的最有效方法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!