100 lines
3.5 KiB
Plaintext
100 lines
3.5 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:sample_sort 3.2.- Sample_Sort]
|
|
|
|
[:
|
|
This is a implementation of the [*[@https://en.wikipedia.org/wiki/Samplesort Samplesort]] algorithm by Francisco Tapia for the Boost Library.
|
|
|
|
It is a highly efficient [*parallel stable sort], optimized for use with many threads.
|
|
|
|
The additional memory needed is of the same size than the data
|
|
]
|
|
|
|
[section:sample_description Description]
|
|
[:
|
|
|
|
[*[teletype]
|
|
``
|
|
| | | |
|
|
Algorithm |Stable | Additional memory |Best, average, and worst case |
|
|
----------------------+-------+------------------------+------------------------------+
|
|
sample_sort | yes | N | N, N LogN , N LogN |
|
|
| | | |
|
|
``
|
|
]
|
|
|
|
You can see their performance in the [*[link sort.parallel.linux_parallel Benchmarks]] chapter
|
|
]
|
|
[endsect]
|
|
|
|
[section:sample_programming Programming]
|
|
[:
|
|
[h4[_Thread Specification]]
|
|
|
|
[:
|
|
This algorithm has an integer parameter indicating the *number of threads* to use in the sorting process,
|
|
which always is the last value in the call. The default value (if left unspecified) is the number of HW threads of
|
|
the machine where the program is running provided by std::thread::hardware_concurrency().
|
|
|
|
If the number is 1 or 0, the algorithm runs with only 1 thread.
|
|
|
|
The number of threads is not a fixed number, but is calculated in each execution. The number of threads passed can be greater
|
|
than the number of hardware threads on the machine. We can pass 100 threads in a machine with 4 HW threads,
|
|
and in the same mode we can pass a function as (std::thread::hardware_concurrency() / 4 ).
|
|
If this value is 0, the program is executed with 1 thread.
|
|
|
|
]
|
|
|
|
[h4[_Programming]]
|
|
[:
|
|
You only need to include the file boost/sort/sort.hpp.
|
|
|
|
The algorithm run in the namespace boost::sort
|
|
|
|
[c++]
|
|
``
|
|
#include <boost/sort/sort.hpp>
|
|
|
|
|
|
template <class iter_t>
|
|
void sample_sort (iter_t first, iter_t last);
|
|
|
|
template <class iter_t, typename compare>
|
|
void sample_sort (iter_t first, iter_t last, compare comp);
|
|
|
|
template <class iter_t>
|
|
void sample_sort (iter_t first, iter_t last, uint32_t num_thread);
|
|
|
|
template <class iter_t, typename compare>
|
|
void sample_sort (iter_t first, iter_t last, compare comp, uint32_t num_thread);
|
|
|
|
``
|
|
|
|
This algorithm needs a *C++11 compliant compiler*, and doesn't need any other code or library. Correct operation is not guaranteed with older compilers.
|
|
|
|
If the number of threads is unspecified, this uses the result of std::thread::hardware_concurrency().
|
|
|
|
This algorithm uses a *comparison object*, in the same way as the standard library sort
|
|
algorithms. If not defined, the comparison object is std::less, which uses
|
|
the < operator internally.
|
|
|
|
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 in the copy constructor.. ) the results can be
|
|
unpredictable.
|
|
]
|
|
]
|
|
[endsect]
|
|
|
|
[endsect]
|
|
|
|
|
|
|