1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Float Sort</title>
<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.78.1">
<link rel="home" href="../../index.html" title="Boost.Sort">
<link rel="up" href="../sort_hpp.html" title="Spreadsort">
<link rel="prev" href="integer_sort.html" title="Integer Sort">
<link rel="next" href="string_sort.html" title="String Sort">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="integer_sort.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../sort_hpp.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="string_sort.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="sort.sort_hpp.float_sort"></a><a class="link" href="float_sort.html" title="Float Sort">Float Sort</a>
</h3></div></div></div>
<p>
<code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/float_sort_idp47034528.html" title="Function template float_sort">float_sort</a></code></code>
is a fast templated in-place hybrid radix/comparison algorithm much like
<code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/integer_sort_idp41299456.html" title="Function template integer_sort">integer_sort</a></code></code>,
but sorts IEEE floating-point numbers (positive, zero, NaN, and negative)
into ascending order by casting them to integers. This works because positive
IEEE floating-point numbers sort like integers with the same bits, and negative
IEEE floating-point numbers sort in the reverse order of integers with the
same bits. float_sort is roughly 2X as fast as std::sort.
</p>
<p>
-0.0 vs. 0.0 and NaN are given definitive ordered positions by the radix-based
portion of this algorithm, where comparison-based sorting does not guarantee
their relative position. The included tests avoid creating NaN and -0.0 so
that results match std::sort, which is not consistent in how it handles these
numbers, as they compare as equal to numbers with different values.
</p>
<p>
float_sort checks the size of the data type and whether it is castable, picking
an integer type to cast to, if a casting functor isn't provided by the user.
</p>
<p>
float_mem_cast casts IEEE floating-point numbers (positive, zero, NaN, and
negative) into integers. This is an essential utility for creating a custom
rightshift functor for float_sort, when one is needed. Only IEEE floating-point
numbers of the same size as the integer type being cast to should be used
in this specialized method call. Worst-case performance is <span class="emphasis"><em>𝑶(N *
(log2(range)/s + s))</em></span>, so <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/float_sort_idp47034528.html" title="Function template float_sort">float_sort</a></code></code>
is asymptotically faster than pure comparison-based algorithms. <span class="emphasis"><em>s</em></span>
is <span class="emphasis"><em>max_splits</em></span>, which defaults to 11, so its worst-case
with default settings for 32-bit integers is <span class="emphasis"><em>𝑶(N * ((32/11)</em></span>
slow radix-based iterations + 11 fast comparison-based iterations).
</p>
<p>
Some performance plots of runtime vs. n and log2(range) are provided below:
</p>
<p>
<a href="../../../../doc/graph/windows_float_sort.htm" target="_top">Windows Float Sort</a>
</p>
<p>
<a href="../../../../doc/graph/osx_float_sort.htm" target="_top">OSX Float Sort</a>
</p>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="sort.sort_hpp.float_sort.floatsort_examples"></a><a class="link" href="float_sort.html#sort.sort_hpp.float_sort.floatsort_examples" title="Float Sort Examples">Float
Sort Examples</a>
</h4></div></div></div>
<p>
See <a href="../../../../example/floatfunctorsample.cpp" target="_top">floatfunctorsample.cpp</a>
for a working example of how to sort structs with a float key:
</p>
<pre class="programlisting"><span class="preprocessor">#define</span> <span class="identifier">CAST_TYPE</span> <span class="keyword">int</span>
<span class="preprocessor">#define</span> <span class="identifier">KEY_TYPE</span> <span class="keyword">float</span>
</pre>
<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">DATA_TYPE</span> <span class="special">{</span>
<span class="identifier">KEY_TYPE</span> <span class="identifier">key</span><span class="special">;</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">data</span><span class="special">;</span>
<span class="special">};</span>
</pre>
<p>
Right-shift functor:
</p>
<pre class="programlisting"><span class="comment">// Casting to an integer before bitshifting</span>
<span class="keyword">struct</span> <span class="identifier">rightshift</span> <span class="special">{</span>
<span class="keyword">int</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&</span><span class="identifier">x</span><span class="special">,</span> <span class="keyword">const</span> <span class="keyword">unsigned</span> <span class="identifier">offset</span><span class="special">)</span> <span class="keyword">const</span> <span class="special">{</span>
<span class="keyword">return</span> <span class="identifier">float_mem_cast</span><span class="special"><</span><span class="identifier">KEY_TYPE</span><span class="special">,</span> <span class="identifier">CAST_TYPE</span><span class="special">>(</span><span class="identifier">x</span><span class="special">.</span><span class="identifier">key</span><span class="special">)</span> <span class="special">>></span> <span class="identifier">offset</span><span class="special">;</span>
<span class="special">}</span>
<span class="special">};</span>
</pre>
<p>
Comparison lessthan <code class="computeroutput"><span class="keyword">operator</span><span class="special"><</span></code> functor:
</p>
<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">lessthan</span> <span class="special">{</span>
<span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&</span><span class="identifier">x</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&</span><span class="identifier">y</span><span class="special">)</span> <span class="keyword">const</span> <span class="special">{</span>
<span class="keyword">return</span> <span class="identifier">x</span><span class="special">.</span><span class="identifier">key</span> <span class="special"><</span> <span class="identifier">y</span><span class="special">.</span><span class="identifier">key</span><span class="special">;</span>
<span class="special">}</span>
<span class="special">};</span>
</pre>
<p>
Other examples:
</p>
<p>
<a href="../../../../example/double.cpp" target="_top">Sort doubles.</a>
</p>
<p>
<a href="../../../../example/shiftfloatsample.cpp" target="_top">Sort floats using a rightshift
functor.</a>
</p>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2014 Steven Ross<p>
Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
Software License, Version 1.0</a>.
</p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="integer_sort.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../sort_hpp.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="string_sort.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
