Могу ли я выполнить поиск в двоичном дереве со стандартной библиотекой без переноса типа float и злоупотребления BTreeMap?

Question

Я хотел бы найти первый элемент, который больше, чем предел из упорядоченной коллекции . Хотя итерация по нему всегда возможна, мне нужна более быстрая. В настоящее время я придумала решение типа 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? Я знаю, что есть много реализаций дерева, но это похоже на излишество.

После предложений в ответе использовать итератор я провел небольшой тест со следующим кодом:

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

Вы сказали, что хотите использовать решение только для std, но это достаточно распространенная проблема, поэтому вот решение с использованием ящика ordered-float:

Cargo.toml

[dependencies]
ordered-float = "1.0"

main.rs

use ordered_float::OrderedFloat; // 1.0.2
use std::collections::BTreeMap;

fn main() {
    let mut ww = BTreeMap::new();
    ww.insert(OrderedFloat(1.0), "one");
    ww.insert(OrderedFloat(2.0), "two");
    ww.insert(OrderedFloat(3.0), "three");
    ww.insert(OrderedFloat(4.0), "three");
    let rez = ww.range(OrderedFloat(1.5)..).next().map(|(_, &v)| v);

    println!("{:?}", rez);
}

отпечатки

Some("two")

А разве это не красиво и чисто? Если вам нужен менее подробный синтаксис, я предлагаю обернуть сам BTreeMap, чтобы вы могли дать ему подходящие имена методов, которые имеют смысл для вашего приложения.

Поведение NaN

Имейте в виду, что OrderedFloat может вести себя не так, как вы ожидаете, в присутствии NaN :

NaN сортируется как больше , чем все другие значения, и равно для себя, что противоречит стандарту IEEE.

Answer 2

Теперь, когда мы немного уточнили требования, есть пара плохих новостей для вас:

1. Вы не избавляетесь от необходимости иметь тип упаковки. Как я уверен, вы обнаружили, что это потому, что ни один тип с плавающей точкой не реализует Ord
2. Вы также не избавляетесь от какого-либо комбинатора

Во-первых, мы собираемся прояснить ваш impl, поскольку у них обоих есть недостатки, описанные в комментариях. В будущем, возможно, имеет смысл использовать черты оболочки в eq-float, поскольку они уже все это реализуют. Реализации по вине это PartialEq и Ord, и они оба разбиты на несколько пунктов. Новые реализации:

impl Ord for FloatWrapper {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.partial_cmp(&other.0).unwrap_or_else(|| {
            if self.0.is_nan() && !other.0.is_nan() {
                Ordering::Less
            } else if !self.0.is_nan() && other.0.is_nan() {
                Ordering::Greater
            } else {
                Ordering::Equal
            }
        })
    }
}
impl PartialEq for FloatWrapper {
    fn eq(&self, other: &Self) -> bool {
        if self.0.is_nan() && other.0.is_nan() {
            true
        } else {
            self.0 == other.0
        }
    }
}

Ничего удивительного, мы просто злоупотребляем тем фактом, что f32 реализует PartialOrd для Ord и выходят на поверхность всех других реализаций на FloatWrapper.

Теперь для комбинатора. Ваш текущий комбинатор заставит ряд элементов временно сохранить в памяти, чтобы затем удалить один. Мы можем добиться большего, злоупотребляя тем фактом, что iter() является отсортированным итератором. Таким образом, мы можем пропустить во время поиска, а затем взять первое:

        let mut first_element = ww.iter()
            .skip_while(|(i, _)| *i < &FloatWrapper::new(1.5)) // Skipping all elements before it
            .take(1) // Reducing the iterator to 1 element
            .map(|(_, &v)| v) // Getting its value, dereferenced
            .next(); // Our result

Это дает ускорение на 10% в ситуациях с низким числом элементов по сравнению с вашей первой реализацией.