☰

浮動小数点数のベクトルに対してバイナリ検索を実行するにはどうすればいいですか? 質問する

tag-icon • tag-icon rust
浮動小数点数のベクトルに対してバイナリ検索を実行するにはどうすればいいですか? 質問する

Vec<u32>もしあなたがslice::binary_search方法。

理由はわかりませんf32が、f64実装していませんOrd。プリミティブ型は標準ライブラリからのものであるため、Ord自分で実装することはできないため、このメソッドを使用することはできないようです。

これを効果的に行うにはどうすればよいでしょうか?

f64本当にラッパー構造体でラップして実装する必要がありますか? これを実行するのは非常に面倒で、事実上何の理由もなくデータのブロックを安全でない方法でやり取りするOrd手間がかかります。transmute

ベストアンサー1

理由はわかりませんが、f32 と f64 は Ord を実装していません。

なぜなら浮動小数点数が難しい! 簡単に言うと、浮動小数点数は特別な値 NaN (Not a Number) を持ちます。浮動小数点数の 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);
}

おすすめ記事