如何对浮点数的 Vec 进行二分搜索? [英] How to do a binary search on a Vec of floats?

问题描述

如果你有一个 Vec 你会使用 slice::binary_search 方法.

If you have a Vec<u32> you would use the slice::binary_search method.

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

For reasons I don't understand, f32 and f64 do not implement Ord. Since the primitive types are from the standard library, you cannot implement Ord on them yourself, so it does not appear you can use this method.

你如何有效地做到这一点?

How can you effectively do this?

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

Do I really have to wrap f64 in a wrapper struct and implement Ord on it? It seems extremely painful to have to do this, and involves a great deal of transmute to cast blocks of data back and forth unsafely for effectively no reason.

推荐答案

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

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

因为浮点很难！简短版本是浮点数具有特殊值 NaN - Not a Number.浮点数的 IEEE 规范指出 1 <;NaN, 1 >NaN 和 NaN == NaN 都是 false.

Because floating point is hard! The short version is that floating point numbers have a special value NaN - Not a Number. The IEEE spec for floating point numbers states that 1 < NaN, 1 > NaN, and NaN == NaN are all false.

Ord 说:

形成全序的类型的特征.

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

This means that the comparisons need to have totality:

a ≤ b 或 b ≤ a

a ≤ b or b ≤ a

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

but we just saw that floating points do not have this property.

是的，您需要创建一个包装器类型，以某种方式处理比较大量 NaN 值.也许你的情况你可以断言浮点值永远不是 NaN 然后调用常规 PartialOrd 特性.举个例子:

So yes, you will need to create a wrapper type that somehow deals with comparing the 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 trait. Here's an example:

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

这篇关于如何对浮点数的 Vec 进行二分搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！