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
|
[/===========================================================================
Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters
Distributed under the Boost Software License, Version 1.0
See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt
=============================================================================/]
[section:flat_stable_sort 2.4.- flat_stable_sort]
[section:flat_stable_sort_description Description]
[:
[*Flat_stable_sort] is a new stable sort algorithm, designed and implemented by Francisco Jose Tapia for the Boost Sort Library
The goal of the algorithm is to stably sort with little additional memory (about 1% of the memory used by the data).
The default stable sort algorithms provided by most compilers and libraries use substantial additional memory, usually half of the data to sort.
This new algorithm provides around 80%-90% of the speed of the spinsort and the stable sort algorithms provided by compilers and libraries.
This algorithm is fast when the data is almost sorted. Many times the new elements are inserted at the end of the sorted elements,
or some elements are modified, breaking the order of the elements. In these cases, the flat_stable_sort algorithm is very fast.
[*[teletype]
``
| | | |
Algorithm | Stable | Additional Memory | Best, average, and worst case |
-----------------+---------+-----------------------------+--------------------------------+
flat_stable_sort | Yes | size of the data / 256 + 8K | N, NlogN , NlogN |
| | | |
``
]
]
[:
[h4[_Memory Used]]
Memory used by the stable sort algorithms measured on Linux x64
[*[teletype]
``
Algorithm | Memory used |
-------------------+--------------+
std::stable_sort | 1177 MB |
spinsort | 1175 MB |
flat_stable_sort | 788 MB |
-------------------+--------------+
``
]
]
[endsect]
[section:flat_stable_sort_benchmark Benchmark]
[:
The benchmark with 100000000 64 bits integers,comparing with std::stable_sort of GCC 6.3 compiler and spinsort, running on a Intel i7-5820K CPU @ 3.30GH shows the mentioned characteristics.
[*[teletype]
``
Data |std::stable_sort| spin_sort |flat_stable_sort |
-----------------------------+----------------+------------+-----------------+
random | 8.62 | 9.73 | 10.80 |
| | | |
sorted | 4.88 | 0.06 | 0.07 |
sorted + 0.1% end | 4.92 | 0.41 | 0.36 |
sorted + 1% end | 4.97 | 0.55 | 0.49 |
sorted + 10% end | 5.73 | 1.32 | 1.40 |
| | | |
sorted + 0.1% middle | 6.58 | 1.89 | 2.61 |
sorted + 1% middle | 7.06 | 2.12 | 3.07 |
sorted + 10% middle | 9.56 | 4.02 | 5.49 |
| | | |
reverse sorted | 0.13 | 0.14 | 1.87 |
reverse sorted + 0.1% end | 5.22 | 0.52 | 0.42 |
reverse sorted + 1% end | 5.29 | 0.66 | 0.55 |
reverse sorted + 10% end | 6.03 | 1.45 | 1.44 |
| | | |
reverse sorted + 0.1% middle | 6.52 | 1.89 | 2.54 |
reverse sorted + 1% middle | 7.09 | 2.12 | 3.09 |
reverse sorted + 10% middle | 9.46 | 4.02 | 5.53 |
| | | |
-----------------------------+----------------+------------+-----------------+
``
]
If you want detailed information about this algorithm you can find it in the [@../papers/flat_stable_sort_eng.pdf flat_stable_sort_en.pdf document]
]
[endsect]
[section:flat_stable_sort_programming Programming]
[:
You only need to include the file boost/sort/sort.hpp.
The flat_stable_sort function is in the namespace boost::sort.
[c++]
``
#include <boost/sort/sort.hpp>
template <class iter_t, typename compare>
void flat_stable_sort (iter_t first, iter_t last, compare comp = compare());
``
This algorithm uses a [*comparison object], in the same way as the standard library sort
algorithms. If you don't define it, the comparison object defaults to std::less, which uses
the < operator internally for comparisons.
This algorithm is [*exception safe], meaning that, the exceptions generated by the algorithm
guarantee the integrity of the objects to sort, but not their relative order. If the exception
is generated inside the objects (in the move or copy constructors) the results are undefined.
]
[endsect]
[endsect]
|
