18

バイナリ ヒープにフロートを設定したい。具体的には、最小ヒープを実装したい。

フロートはサポートOrdされていないようで、そのままでは使用できません。それらをラップする私の試みは、これまでのところ失敗しています。ただし、それらをラップできれば、最小ヒープOrdを効果的に作成するような方法で実装することもできるようです。BinaryHeap

私が試したラッパーの例を次に示します。

#[derive(PartialEq, PartialOrd)]
struct MinNonNan(f64);

impl Eq for MinNonNan {}

impl Ord for MinNonNan {
    fn cmp(&self, other: &MinNonNan) -> Ordering {
        let ord = self.partial_cmp(other).unwrap();
        match ord {
            Ordering::Greater => Ordering::Less,
            Ordering::Less => Ordering::Greater,
            Ordering::Equal => ord
        }
    }
}

問題はpop、それが最大ヒープであるかのように値を返すことです。

最小ヒープとして値を入力するBinaryHeapには、正確に何をする必要がありますか?f64

4

2 に答える 2

16

クレートベースのソリューション

独自の を記述する代わりに、 ordered-floatクレート +タイプのMinNonNan使用を検討してください。std::cmp::Reverse

type MinNonNan = Reverse<NotNan<f64>>;

手動ソリューション

#[derive]ingPartialOrdであるため、.gt(), .lt()etc メソッドは通常どおり比較されます。つまりMinNonNan(42.0) < MinNonNan(47.0)、まだ true です。Ord境界は、厳密に順序付けられた型を提供することを制限するだけであり、実装がどこでも / / / の代わりに使用することを意味するわけではなく、コンパイラーが.cmp()それらの演算子を突然変更して実装を使用することも意味しません。<><=>=Ord

順序を反転させたい場合はPartialOrd、同様に実装する必要があります。

#[derive(PartialEq)]
struct MinNonNan(f64);

impl PartialOrd for MinNonNan {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl Ord for MinNonNan {
    fn cmp(&self, other: &MinNonNan) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}
于 2016-10-10T01:16:59.787 に答える
9

実施例

クレートベースのソリューション

use ordered_float::NotNan; // 2.7.0
use std::{cmp::Reverse, collections::BinaryHeap};

fn main() {
    let mut minheap = BinaryHeap::new();
    minheap.push(Reverse(NotNan::new(2.0).unwrap()));
    minheap.push(Reverse(NotNan::new(1.0).unwrap()));
    minheap.push(Reverse(NotNan::new(42.0).unwrap()));
    if let Some(Reverse(nn)) = minheap.pop() {
        println!("{}", nn.into_inner());
    }
}

手動ソリューション

use std::{cmp::Ordering, collections::BinaryHeap};

#[derive(PartialEq)]
struct MinNonNan(f64);

impl Eq for MinNonNan {}

impl PartialOrd for MinNonNan {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl Ord for MinNonNan {
    fn cmp(&self, other: &MinNonNan) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

fn main() {
    let mut minheap = BinaryHeap::new();
    minheap.push(MinNonNan(2.0));
    minheap.push(MinNonNan(1.0));
    minheap.push(MinNonNan(42.0));
    if let Some(MinNonNan(root)) = minheap.pop() {
        println!("{:?}", root);
    }
}
于 2016-10-11T20:14:39.957 に答える