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?
4 Likes
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]);
}
17 Likes
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)
}
}
6 Likes
Thanks! What is the meaning of NNAN?
"Negative NaN".
quickersort supports sorting floats.
2 Likes
I happened to have this problem today and this topic was #1 while searching on DuckDuckGo. While @DanielKeep's solution seems very complete, it also seems like a bit of pain to include in my code. quickersort's README mentions it's deprecated. However, I found the ordered-float crate which seems to fit the bill quite nicely.
2 Likes
To add another alternative, my current favorite make-floating-point-less-painful crate is decorum.
4 Likes
5 years later, DanielKeep's suggestion above is available in nightly (not stable yet): https://doc.rust-lang.org/nightly/std/primitive.f64.html#method.total_cmp
That'll probably be the way to go eventually, and has the advantage of also deterministically ordering things like -0.0 vs +0.0.
EDIT: further update for anyone who ends up here, f32::total_cmp is stable as of Rust 1.62 (June 2022).
6 Likes
This topic was automatically closed after 13 days. We invite you to open a new topic if you have further questions or comments.