Как сделать бинарный поиск на Vec плавающих?

Если у вас есть Vec<u32>, вы должны использовать метод slice::binary_search.

По причинам, которые я не понимаю, f32 и f64 не реализуют Ord. Поскольку примитивные типы из стандартной библиотеки, вы не можете реализовать Ord на них самостоятельно, так что, похоже, вы не можете использовать этот метод.

Как вы можете это сделать?

Мне действительно нужно обернуть f64 в структуру обертки и реализовать Ord на нем? Кажется крайне болезненным, что нужно это делать и вовлекает много transmute, чтобы отличать блоки данных взад и вперед неудобно для эффективного использования без причины.

Ответ 1

по причинам, которые я не понимаю, f32 и f64 не реализуют Ord.

Потому что с плавающей точкой сложно ! Короче говоря, числа с плавающей запятой имеют специальное значение NaN - не число. Спецификация IEEE для чисел с плавающей запятой гласит, что 1 < NaN, 1 > NaN и NaN == NaN - все false.

Ord говорит:

Черта для типов, которые формируют общий заказ.

Это означает, что сравнения должны иметь совокупность:

a ≤ b или b ≤ a

но мы только что увидели, что плавающие точки не имеют этого свойства.

Так что да, вам нужно будет создать тип-обертку, который каким-то образом будет иметь дело со сравнением большого количества значений NaN. Возможно, в вашем случае вы можете просто утверждать, что значение с плавающей точкой никогда не равно NaN, а затем вызывать обычную черту PartialOrd. Вот пример:

use std::cmp::Ordering;

#[derive(PartialEq,PartialOrd)]
struct NonNan(f64);

impl NonNan {
    fn new(val: f64) -> Option<NonNan> {
        if val.is_nan() {
            None
        } else {
            Some(NonNan(val))
        }
    }
}

impl Eq for NonNan {}

impl Ord for NonNan {
    fn cmp(&self, other: &NonNan) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

fn main() {
    let mut v: Vec<_> = [2.0, 1.0, 3.0].iter().map(|v| NonNan::new(*v).unwrap()).collect();
    v.sort();
    let r = v.binary_search(&NonNan::new(2.0).unwrap());
    println!("{:?}", r);
}

Ответ 2

Один из методов среза - это binary_search_by, который вы можете использовать. f32/f64 реализован PartialOrd, поэтому, если вы знаете, что они никогда не могут быть NaN, вы можете развернуть результат partial_cmp:

fn main() {
    let values = [1.0, 2.0, 3.0, 4.0, 5.0];
    let location = values.binary_search_by(|v| {
        v.partial_cmp(&3.14).expect("Couldn't compare values")
    });

    match location {
        Ok(i) => println!("Found at {}", i),
        Err(i) => println!("Not found, could be inserted at {}", i),
    }
}

Ответ 3

https://github.com/emerentius/ord_subset реализует метод ord_subset_binary_search(), который вы можете использовать для этого.

из README:

let mut s = [5.0, std::f64::NAN, 3.0, 2.0];
s.ord_subset_sort();
assert_eq!(&s[0..3], &[2.0, 3.0, 5.0]);
assert_eq!(s.ord_subset_binary_search(&5.0), Ok(2));

assert_eq!(s.iter().ord_subset_max(), Some(&5.0));
assert_eq!(s.iter().ord_subset_min(), Some(&2.0));

Ответ 4

Если вы уверены, что ваши значения с плавающей точкой никогда не будут NaN, вы можете выразить эту семантику с помощью упаковщиков в decorum. В частности, тип Ordered реализует Ord и вызывает панику всякий раз, когда программа пытается сделать что-то недопустимое:

use decorum::Ordered;

fn foo() {
    let ordered = Ordered<f32>::from_inner(10.);
    let normal = ordered.into()
}