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

Question

如果你有,Vec<u32>你会使用该slice::binary_search方法.

由于我不理解的原因,f32并且f64没有实施Ord.由于基本类型来自标准库,因此您无法Ord自己实现它们,因此您似乎无法使用此方法.

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

我真的必须包装f64一个包装器结构并Ord在其上实现吗？这样做似乎非常痛苦,并且涉及大量transmute不安全地来回传播数据块,实际上是没有理由的.

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

Answer 2

从 Rust 1.62.0 开始，名为 float 的内置全序比较方法.total_cmp()现已稳定。这实现了 IEEE 754 中定义的总排序，每个可能的f64位值都被明确排序，包括正零和负零，以及所有可能的 NaN。

浮动仍然不会实现Ord，所以它们不会直接排序，但样板已被削减为单行，没有任何外部导入或恐慌的机会：

fn main() {
    let mut v: Vec<f64> = vec![2.0, 2.5, -0.5, 1.0, 1.5];
    v.sort_by(f64::total_cmp);

    let target = 1.25;
    let result = v.binary_search_by(|probe| probe.total_cmp(&target));

    match result {
        Ok(index) => {
            println!("Found target {target} at index {index}.");
        }
        Err(index) => {
            println!("Did not find target {target} (expected index was {index}).");
        }
    }
}

Answer 3

binary_search_by您可以使用切片方法之一.f32/ f64implement 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),
    }
}