如何对浮点数的 Vec 进行二分查找？

Question

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

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

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

我真的必须将 f64 包装在包装器结构中并在其上实现 Ord 吗？必须这样做似乎非常痛苦，并且涉及大量 transmute 无缘无故地不安全地来回投射数据块。

Answer 1

for reasons I don't understand, f32 and f64 do not implement Ord.

因为floating point is hard！简短的版本是浮点数有一个特殊的值 NaN - Not a Number。浮点数的 IEEE 规范指出 1 < NaN、1 > NaN 和 NaN == NaN 都是 false.

Ord 说：

Trait for types that form a total order.

这意味着比较需要总数:

a ≤ b or b ≤ a

但是我们刚刚看到浮点数没有这个属性.

所以是的，您需要创建一个包装器类型，以某种方式处理比较 large number of NaN values. Maybe your case you can just assert that the float value is never NaN and then call out to the regular 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，你可以展开 [=] 的结果16=]:

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. Specifically, the type Ordered 实现中的包装器来表达这种语义 Ord 并在程序尝试执行无效操作时出现恐慌：

use decorum::Ordered;

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

Answer 5

A built-in total-ordering 名为 .total_cmp() is available on nighty, and should be on stable within a couple months, baring any surprising issues. (The vote to stablize the feature recently passed 的浮点数比较方法。）这实现了 IEEE 754 中定义的总排序，每个可能的 f64 位值都是明确排序，包括正零和负零，以及所有可能的 NaN。

Floats 仍然不会实现 Ord，因此它们不会直接排序，但样板已被缩减为一行，没有任何外部导入或恐慌的机会：

#![feature(total_cmp)]

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

如何对浮点数的 Vec 进行二分查找？

How to do a binary search on a Vec of floats?

rust