Wie mache ich eine binäre Suche auf einem Vec von Schwimmern?

Question

Wenn Sie eine Vec<u32> haben, würden Sie die slice::binary_search Methode verwenden.

Aus Gründen, die ich nicht verstehe, f32 und f64 implementieren Sie nicht Ord. Da die primitiven Typen aus der Standardbibliothek stammen, können Sie Ord nicht selbst implementieren, so dass Sie diese Methode nicht verwenden können.

Wie können Sie das effektiv tun?

Muss ich wirklich f64 in eine Wrapper-Struktur wickeln und Ord darauf implementieren? Es scheint extrem schmerzhaft zu sein, dies zu tun, und involviert eine Menge von transmute, um Blöcke von Daten unsicher und ohne Grund zu werfen.

Answer 1

aus Gründen, die ich nicht verstehe, f32 und f64 nicht implementieren Ord.

Weil floating point is hard! Die kurze Version ist, dass Fließkommazahlen einen speziellen Wert NaN - keine Zahl haben. Die IEEE-Spezifikation für Fließkommazahlen besagt, dass 1 < NaN, 1 > NaN und NaN == NaN alle false sind.

Ord sagt:

Trait für Typen, die eine total order bilden.

Dies bedeutet, dass die Vergleiche Gesamtheit haben müssen:

a ≤ b oder b ≤ a

aber wir sahen nur, dass Gleitpunkte diese Eigenschaft nicht haben.

Also ja, Sie müssen einen Wrappertyp erstellen, der sich irgendwie damit beschäftigt, die large number of NaN values zu vergleichen. Vielleicht kannst du einfach behaupten, dass der Float-Wert niemals NaN ist und dann zum regulären PartialOrd-Merkmal aufruft. Hier ein Beispiel:

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

Einer der Scheibe Methoden ist binary_search_by, die Sie nutzen könnten. f32/f64PartialOrd implementieren, so dass, wenn Sie wissen, dass sie nie NaN sein, das Ergebnis von partial_cmp auspacken kann:

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 3

https://github.com/emerentius/ord_subset implementiert eine ord_subset_binary_search() Methode, die Sie für diese verwenden können.

aus ihrer 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));