3 ms·
Of 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
by stabbles 8y ago
Of 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.