我可以在不包装float类型和滥用BTreeMap的情况下使用标准库执行二叉树搜索吗？

Question

我想从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倍的加速（至少基于此微基准测试）。

我想从有序集合中找到第一个大于限制的元素。尽管迭代总是一个选择，但我需要一个更快的选择。目前，我想出了一个解决方案...

Answer 1

现在我们已经过了，并澄清了一些要求，对您来说有两个坏消息：

Answer 2

[您说过，您只需要一个std解决方案，但这是一个很常见的问题，所以这里是一个使用板条箱ordered-float的解决方案：