如何对一个包含浮点数的Vec进行二分查找？

Question

如果你有一个Vec<u32>，你可以使用slice::binary_search方法。

由于我不理解的原因，f32和f64没有实现Ord。由于这些基本类型来自标准库，你不能自己在它们上面实现Ord，因此似乎不能使用这种方法。

你该如何有效地做到这一点？

我真的必须将f64包装在一个包装结构中，并在其上实现Ord吗？这似乎非常麻烦，涉及大量的transmute来不安全地转换数据块，实际上没有任何理由。

- Doug

---

f32和f64没有完全的排序，因为根据IEEE 754，NaN值不等于、大于或小于任何其他浮点值。 - RBF06

Answer 1

由于某些我不理解的原因，f32和f64不实现Ord。

因为浮点数很难！简短的解释是，浮点数有一个特殊值NaN-非数字。 IEEE浮点数规范指出1 < NaN，1 > NaN和 NaN == NaN 都是 false 。 Ord表示：

用于形成全序类型的Trait。

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

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

- Shepmaster

---

其中一种切片扩展方法是binary_search_by，您可以使用它。 f32/f64 实现了PartialOrd，因此如果您知道它们永远不会是 NaN，则可以解包 partial_cmp 的结果：http://doc.rust-lang.org/std/slice/trait.SliceExt.html#tymethod.binary_search_by - BurntSushi5

可以使用 ordered_float 或 ord_subset crate。请参见 https://dev59.com/15bfa4cB1Zd3GeqP0OQy#37144472。 - malbarbo

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

- Shepmaster

Answer 3

自 Rust 1.62.0 起，名为 .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}).");
        }
    }
}

- user18102576

Answer 4

如果您确定浮点数值永远不会是NaN，您可以使用decorum中的包装器来表达这个语义。具体来说，类型Ordered实现了Ord，并在程序尝试执行无效操作时引发异常：

use decorum::Ordered;

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

- Venkat Arun

Answer 5

https://github.com/emerentius/ord_subset 实现了一个ord_subset_binary_search() 方法，你可以用它来完成这个任务。

来自他们的 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));

- TBieniek

Answer 6

你可以使用nutype在你的新类型上使用Ord，并且不需要太多样板代码即可进行finite验证。 finite验证排除了NaN和Infinity，这使得nutype可以安全地派生Ord：

这里是一个示例：

use nutype::nutype;

#[nutype(validate(finite))]
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Float(f64);

fn main() {
    let raw_data = vec![1.1, 2.5, 0.1, 4.5];
    let mut data: Vec<Float> = raw_data
        .into_iter()
        .map(|val| Float::new(val).unwrap())
        .collect();

    data.sort();
    println!("data = {data:?}");

    let idx25 = data.binary_search(&Float::new(2.5).unwrap());
    println!("2.5 index = {idx25:?}");

    let idx36 = data.binary_search(&Float::new(3.6).unwrap());
    println!("3.6 index = {idx36:?}");
}

输出：

data = [Float(0.1), Float(1.1), Float(2.5), Float(4.5)]
2.5 index = Ok(2)
3.6 index = Err(3)

请注意，Float::new(val) 返回 Result。传递类似 Float::new(0.0/0.0) 的值将返回一个错误。

- Sergey Potapov