如何在Vec of Floats上进行二进制搜索？

Question

如果你有Vec<u32>，你会使用slice::binary_search方法。

由于我不明白的原因，f32和f64没有实施Ord。由于原始类型来自标准库，因此您无法自己对它们实现Ord，因此您似乎无法使用此方法。

你怎么能有效地做到这一点？

我真的必须在包装结构中包装f64并在其上实现Ord吗？这样做似乎非常痛苦，并且需要大量的transmute来无情地来回摆放数据块，实际上是没有理由的。

Answer 1

由于我不明白的原因，f32和f64没有实现Ord。

因为floating point is hard！简短版本是浮点数具有特殊值NaN - 非数字。浮点数的IEEE规范指出1 < NaN，1 > NaN和NaN == NaN都是false。

Ord说：

形成total order的类型的特征。

这意味着比较需要具有整体性：

a≤b或b≤a

但我们只是看到浮点没有这个属性。

所以，是的，您将需要创建一个包装类型，以某种方式处理比较large number of NaN values。也许你的情况你可以断言浮动值永远不是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);
}

Answer 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),
    }
}

Answer 3

https://github.com/emerentius/ord_subset实现了一个ord_subset_binary_search()方法，你可以使用它。

从他们的自述文件：

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

Answer 4

如果您确定浮点值永远不会是NaN，则可以使用decorum中的包装器来表达此语义。具体来说，只要程序试图做一些无效的事情，类型Ordered就会实现Ord和恐慌：

use decorum::Ordered;

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