5 ms·
> the escape hatch suggested on the internet, `partial_cmp(...).unwrap_or(Ordering::Less)` This is often a Bad Idea, as you get unstable sorts and you are rig
by shepmaster 8y ago
> the escape hatch suggested on the internet, `partial_cmp(...).unwrap_or(Ordering::Less)`
This is often a Bad Idea, as you get unstable sorts and you are right back to the same problem.
- Explanation: How do I get the minimum or maximum value of an iterator containing floating point numbers? — https://stackoverflow.com/a/50308360/155423 https://stackoverflow.com/a/50308360/155423
- Example: https://play.integer32.com/?version=stable&mode=debug&edition=2018&gist=d459a0de3fc4dce15a090d078cf8f15e https://play.integer32.com/?version=stable&mode=debug&editio...
See also:
- How to do a binary search on a Vec of floats? — https://stackoverflow.com/q/28247990/155423 https://stackoverflow.com/q/28247990/155423
Instead, use a wrapper type or raise a panic.
- stabbles 8y agoIsn't there a default total order for floats? E.g. -Inf < -1.0 < -0.0 < 0.0 < 1.0 < Inf < NaN?
- achamayou 8y agoNo, because x < NaN and x > NaN are false for any value of x.
- stabbles 8y agoYes, the literal < in the language induces a partial order by convention. What I'm getting at in my comment is that you can define a sensible total ordering.
- wyldfire 8y agoThe challenge becomes what code to emit when you see those operators: native target comparisons, or the software implementation of your total ordering? The latter is safe and slow and the former is fast and IMO idiomatic. So since no one needs this often enough to emit the soft-float comparison code, we should emit the fast code. If folks need different behavior they should use different types. This is similar to the behavior with integer overflow, which you can opt into by using checked types or checked operations. Though in rust we have a convenience that the overflow-detecting code is emitted for debug targets.
- deleted 8y ago[deleted]
- achamayou 8y agoIt is possible to do redefine NaN as something different than what IEEE 754 contains, but it will surprising to some users, and it will come at a performance cost because you can no longer let the hardware handle all float comparisons directly.
- qznc 8y agoYes, there is: https://en.wikipedia.org/wiki/IEEE_754#Total-ordering_predicate https://en.wikipedia.org/wiki/IEEE_754#Total-ordering_predic... It is not something to use by default though. It is implemented in software and thus a lot slower than the hardware comparison.
- dkarl 8y agoI'm curious as to why it isn't implemented in hardware. Is it really so rare to need to sort floats, or so common to need a different ordering when you do?
- stabbles 8y agoOf course sorting floats happens a lot. In practice one rarely encounters NaN's and ±Inf's, so fast comparison for concrete values is the default. I don't know why the 'slow' total order is not implemented in hardware though. But fortunately in comparison sort algorithms that run in O(n lg n) you can get away with doing an O(n) partitioning of the array into [-, +, NaN] and then applying a fast integer comparison operator to the negative values (-) and positive values (+). In fact the above idea ties in neatly with QuickSort, which is already based on partitioning & sorting recursively.
- bsder 8y ago> Of course sorting floats happens a lot. Is this true? I am actually struggling to remember the last time I did a sort with a float/double as the key--especially in a performance bounded context ... <thinking> ... Aha. Graphic engine. Octtree with coordinates. I really had to think about that. So, I'm a bit skeptical of float sorting happening a "lot". Is this perhaps an ML primitive somewhere?
- harrisi 8y agoLanguages that only have floats, such as JavaScript and Lua, certainly sort floats quite often.
- rusbus 8y agoOP here -- this post is pretty dated. I currently use the OrderedFloat [1] crate to solve this problem which works quite well and plays nicely with NaN https://crates.io/crates/ordered-float https://crates.io/crates/ordered-float
- IshKebab 8y agoTo me this feels quite pedantic. Being able to do less than on NaNs and just having it do something vaguely sensible (as in your linked solution) is a far more common requirement than need to handle NaNs specially. You could even say the reason NaN exists is so that you don't have to check for NaN constantly. Rust is being technically correct but practically really annoying, for basically no benefit.
- steveklabnik 8y agoFor what it's worth, many in the Rust community agree with you. Many people consider this a mistake, in hindsight, though not everyone.