124 lines
5.2 KiB
Plaintext
124 lines
5.2 KiB
Plaintext
[/===========================================================================
|
|
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]
|