rust - ¿Cómo hacer una búsqueda binaria en un Vec de carrozas?

Question

Si tiene un Vec<u32> usaría el método slice::binary_search .

Por razones que no entiendo, f32 y f32 no implementan Ord . Dado que los tipos primitivos son de la biblioteca estándar, no puede implementar Ord en ellos, por lo que no parece que pueda usar este método.

¿Cómo puedes hacer esto de manera efectiva?

¿Realmente tengo que envolver f64 en una estructura de envoltura e implementar Ord en él? Parece extremadamente doloroso tener que hacer esto, e implica una gran cantidad de transmute para enviar bloques de datos de un lado a otro de manera insegura sin ningún motivo efectivo.

Answer 1

por razones que no entiendo, f32 y f64 no implementan Ord.

¡Porque el punto flotante es difícil ! La versión corta es que los números de coma flotante tienen un valor especial NaN - No es un número. La especificación IEEE para números de coma flotante establece que 1 < NaN , 1 > NaN y NaN == NaN son todos false .

Ord dice:

Rasgo para los tipos que forman un orden total .

Esto significa que las comparaciones deben tener totalidad :

a ≤ b o b ≤ a

pero acabamos de ver que los puntos flotantes no tienen esta propiedad.

Entonces, sí, tendrá que crear un tipo de contenedor que de alguna manera trate de comparar la gran cantidad de valores de NaN . Tal vez su caso puede simplemente afirmar que el valor flotante nunca es NaN y luego llamar al rasgo PartialOrd normal. Aquí hay un ejemplo:

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);
}

Answer 2

Si está seguro de que sus valores de coma flotante nunca serán NaN, puede expresar esta semántica con los envoltorios en decorum . Específicamente, el tipo Ordered implementa Ord y entra en pánico cada vez que el programa intenta hacer algo no válido:

use decorum::Ordered;

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

Answer 3

Uno de los métodos de binary_search_by es binary_search_by , que podría usar. f32 / f32 implementa PartialOrd , por lo que si sabe que nunca pueden ser NaN , puede desenvolver el resultado de 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),
    }
}

Answer 4

https://github.com/emerentius/ord_subset implementa un método ord_subset_binary_search() que puede usar para esto.

de su 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));