我想从ordered集合中找到第一个大于限制的元素。尽管迭代总是一个选择,但我需要一个更快的选择。目前,我想出了一个类似this的解决方案,但感觉有点不客气:
use std::cmp::Ordering;
use std::collections::BTreeMap;
use std::ops::Bound::{Included, Unbounded};
#[derive(Debug)]
struct FloatWrapper(f32);
impl Eq for FloatWrapper {}
impl PartialEq for FloatWrapper {
fn eq(&self, other: &Self) -> bool {
(self.0 - other.0).abs() < 1.17549435e-36f32
}
}
impl Ord for FloatWrapper {
fn cmp(&self, other: &Self) -> Ordering {
if (self.0 - other.0).abs() < 1.17549435e-36f32 {
Ordering::Equal
} else if self.0 - other.0 > 0.0 {
Ordering::Greater
} else if self.0 - other.0 < 0.0 {
Ordering::Less
} else {
Ordering::Equal
}
}
}
impl PartialOrd for FloatWrapper {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
浮点数包装不好,即使我确定不会有NaN]]
Range
也是不必要的,因为我想要一个元素。
仅使用Rust的标准库,有没有更好的方法来获得相似的结果?我知道有很多树实现,但是感觉有点过分了。
在使用迭代器的建议in the answer之后,我使用以下代码做了一些基准测试:
fn main() { let measure = vec![ 10, 15, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, ]; let mut measured_binary = Vec::new(); let mut measured_iter = Vec::new(); let mut measured_vec = Vec::new(); for size in measure { let mut ww = BTreeMap::new(); let mut what_found = Vec::new(); for _ in 0..size { let now: f32 = thread_rng().gen_range(0.0, 1.0); ww.insert(FloatWrapper(now), now); } let what_to_search: Vec<FloatWrapper> = (0..10000) .map(|_| thread_rng().gen_range(0.0, 0.8)) .map(|x| FloatWrapper(x)) .collect(); let mut rez = 0; for current in &what_to_search { let now = Instant::now(); let m = find_one(&ww, current); rez += now.elapsed().as_nanos(); what_found.push(m); } measured_binary.push(rez); rez = 0; for current in &what_to_search { let now = Instant::now(); let m = find_two(&ww, current); rez += now.elapsed().as_nanos(); what_found.push(m); } measured_iter.push(rez); let ww_in_vec: Vec<(FloatWrapper, f32)> = ww.iter().map(|(&key, &value)| (key, value)).collect(); rez = 0; for current in &what_to_search { let now = Instant::now(); let m = find_three(&ww_in_vec, current); rez += now.elapsed().as_nanos(); what_found.push(m); } measured_vec.push(rez); println!("{:?}", what_found); } println!("binary :{:?}", measured_binary); println!("iter_map :{:?}", measured_iter); println!("iter_vec :{:?}", measured_vec); } fn find_one(from_what: &BTreeMap<FloatWrapper, f32>, what: &FloatWrapper) -> f32 { let v: Vec<f32> = from_what .range((Included(what), (Unbounded))) .take(1) .map(|(_, &v)| v) .collect(); *v.get(0).expect("we are in truble") } fn find_two(from_what: &BTreeMap<FloatWrapper, f32>, what: &FloatWrapper) -> f32 { from_what .iter() .skip_while(|(i, _)| *i < what) // Skipping all elements before it .take(1) // Reducing the iterator to 1 element .map(|(_, &v)| v) // Getting its value, dereferenced .next() .expect("we are in truble") // Our } fn find_three(from_what: &Vec<(FloatWrapper, f32)>, what: &FloatWrapper) -> f32 { *from_what .iter() .skip_while(|(i, _)| i < what) // Skipping all elements before it .take(1) // Reducing the iterator to 1 element .map(|(_, v)| v) // Getting its value, dereferenced .next() .expect("we are in truble") // Our }
对我来说,主要的收获是值得在大约50个元素之后使用二进制搜索。在我的案例中,使用30000个元素意味着200倍的加速(至少基于此微基准测试)。
我想从有序集合中找到第一个大于限制的元素。尽管迭代总是一个选择,但我需要一个更快的选择。目前,我想出了一个解决方案...
现在我们已经过了,并澄清了一些要求,对您来说有两个坏消息:
[您说过,您只需要一个std解决方案,但这是一个很常见的问题,所以这里是一个使用板条箱ordered-float
的解决方案: