How to sort a Vec of floats?


#1

The trait core::cmp::Ord is not implemented for the type f32 and f64, so we cannot use the sort() method in std for sorting an Vec of floats. Do we need implement it by hand?


#2

slice::sort_by.

fn main() {
    let mut v: [f32; 5] = [5.0, 4.0, 1.0, 3.0, 2.0];
    v.sort_by(|a, b| a.partial_cmp(b).unwrap());
    assert!(v == [1.0, 2.0, 3.0, 4.0, 5.0]);
}

#3

For completeness, here’s an implementation of the total ordering predicate from IEEE 754-2008. I haven’t tested it with varying NaN payloads because I’ve stopped caring at this point.

#![allow(non_snake_case)]

macro_rules! assert_really_eq {
    ($lhs:expr, $rhs:expr) => {
        {
            let left = $lhs;
            let right = $rhs;
            if !left.really_eq(&right) {
                panic!("assertion failed: `(left === right)` (left: `{:?}`, right: `{:?}`)", left, right);
            }
        }
    };
}

fn main() {
    {
        let mut v: [f32; 5] = [5.0, 4.0, 1.0, 3.0, 2.0];
        v.sort_by(|a, b| a.partial_cmp(b).unwrap());
        assert!(v == [1.0, 2.0, 3.0, 4.0, 5.0]);
    }

    {
        use std::f32::{NAN, INFINITY, NEG_INFINITY};
        let NNAN = unsafe {
            use std::mem::transmute;
            transmute::<_, f32>(transmute::<_, u32>(NAN) | 0x8000_0000)
        };

        let mut v: [f32; 7] = [5.0, NAN, 4.0, 1.0, NNAN, 3.0, 2.0];
        v.sort_by(Ieee754::total_cmp);
        assert_really_eq!(v, [NNAN, 1.0, 2.0, 3.0, 4.0, 5.0, NAN]);

        let mut v: [f32; 7] = [5.0, NAN, INFINITY, 1.0, NNAN, -3.0, NEG_INFINITY];
        v.sort_by(Ieee754::total_cmp);
        assert_really_eq!(v, [NNAN, NEG_INFINITY, -3.0, 1.0, 5.0, INFINITY, NAN]);

        let mut v: [f32; 4] = [-1.0, 1.0, 0.0, -0.0];
        v.sort_by(Ieee754::total_cmp);
        assert_really_eq!(v, [-1.0, -0.0, 0.0, 1.0]);
    }
}

use std::cmp::Ordering;

pub trait Ieee754 {
    type Exponent;
    type NanPayload;

    fn exponent(self) -> Self::Exponent;
    fn is_really_neg(self) -> bool;
    fn is_signalling_nan(self) -> bool;
    fn nan_payload(self) -> Self::NanPayload;
    fn total_ord(&self, rhs: &Self) -> bool;
    fn total_cmp(&self, rhs: &Self) -> Ordering;
}

impl Ieee754 for f32 {
    type Exponent = i16;
    type NanPayload = u32;

    #[inline]
    fn exponent(self) -> Self::Exponent {
        use std::mem::transmute;
        unsafe {
            (((transmute::<_, u32>(self) >> 23) & 0xff) - 127) as i16
        }
    }
    
    #[inline]
    fn is_really_neg(self) -> bool {
        use std::mem::transmute;
        unsafe {
            (transmute::<_, u32>(self) & 0x8000_0000) != 0
        }
    }
    
    #[inline]
    fn is_signalling_nan(self) -> bool {
        use std::mem::transmute;
        unsafe {
            ((transmute::<_, u32>(self) >> 22) & 1) != 0
        }
    }
    
    #[inline]
    fn nan_payload(self) -> Self::NanPayload {
        use std::mem::transmute;
        unsafe {
            transmute::<_, u32>(self) & 0x1f_ffff
        }
    }

    #[inline]
    fn total_ord(&self, rhs: &Self) -> bool {
        // IEEE 754-2008 §5.10.
        let lhs = *self;
        let rhs = *rhs;

        if lhs < rhs { return true; }
        if lhs > rhs { return false; }
        if lhs == rhs {
            if lhs.really_eq(&-0.0) && rhs.really_eq(&0.0) { return true; }
            if lhs.really_eq(&0.0) && rhs.really_eq(&-0.0) { return false; }
            let lhs_exp = lhs.exponent();
            let rhs_exp = rhs.exponent();
            if lhs.is_sign_negative() && rhs.is_sign_negative() {
                return lhs_exp >= rhs_exp;
            }
            return lhs_exp <= rhs_exp;
        }

        // x and or y is/are unordered
        match (lhs.is_nan(), lhs.is_really_neg(), rhs.is_nan(), rhs.is_really_neg()) {
            (true, neg,     false, _)       => return neg,
            (false, _,      true, neg)      => return !neg,
            (true, true,    true, false)    => return true,
            (true, false,   true, true)     => return false,
            (true, _,       true, _)        => (),
            _ => unreachable!()
        }

        let lhs_payload = lhs.nan_payload();
        let rhs_payload = rhs.nan_payload();
        let lhs_sig = lhs.is_signalling_nan();
        let rhs_sig = rhs.is_signalling_nan();
        
        match (!lhs.is_really_neg(), lhs_sig, rhs_sig, lhs_payload < rhs_payload) {
            (true, true, false, _) => true,
            (true, false, true, _) => false,
            (true, _, _, c) => c,
            (false, true, false, _) => false,
            (false, false, true, _) => true,
            (false, _, _, c) => !c
        }
    }

    fn total_cmp(&self, rhs: &Self) -> Ordering {
        match (self.total_ord(rhs), rhs.total_ord(self)) {
            (true, false) => Ordering::Less,
            (false, true) => Ordering::Greater,
            (true, true) => Ordering::Equal,
            _ => panic!("could not order {:?}, {:?}", self, rhs)
        }
    }
}

trait ReallyEq {
    fn really_eq(&self, rhs: &Self) -> bool;
}

impl ReallyEq for f32 {
    fn really_eq(&self, rhs: &Self) -> bool {
        use std::mem::transmute;
        unsafe {
            transmute::<_, u32>(*self) == transmute::<_, u32>(*rhs)
        }
    }
}

impl<T> ReallyEq for [T]
where T: ReallyEq {
    fn really_eq(&self, rhs: &Self) -> bool {
        if self.len() != rhs.len() { return false; }
        self.iter().zip(rhs.iter()).all(|(a, b)| a.really_eq(b))
    }
}

impl ReallyEq for [f32; 7] {
    fn really_eq(&self, rhs: &Self) -> bool {
        <[f32] as ReallyEq>::really_eq(self, rhs)
    }
}

#4

Thanks! What is the meaning of NNAN?


#5

“Negative NaN”.


#6

quickersort supports sorting floats.