123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899 |
- [/===========================================================================
- 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:parallel_stable_sort 3.3.- Parallel_stable_sort]
- [section:parallel_description Description]
- [:
- This is an adaptation of the [*[@https://en.wikipedia.org/wiki/Samplesort Samplesort]] algorithm,
- using an additional memory a half of the memory used by the data
- (the original algorithm uses an additional memory as the used by the data).
- It is a highly efficient [*parallel stable sort], optimized for use with many threads.
- [*[teletype]
- ``
- | | | |
- Algorithm |Stable | Additional memory |Best, average, and worst case |
- ----------------------+-------+------------------------+------------------------------+
- parallel_stable_sort | yes | N / 2 | N, N LogN , N LogN |
- | | | |
- ``
- ]
- You can see their performance in the [*[link sort.parallel.linux_parallel Benchmarks]] chapter
- ]
- [endsect]
- [section:parallel_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 to use this code.
- This algorithm run in the namespace boost::sort.
- [c++]
- ``
- #include <boost/sort/sort.hpp>
- template <class iter_t>
- void parallel_stable_sort (iter_t first, iter_t last);
- template <class iter_t, typename compare>
- void parallel_stable_sort (iter_t first, iter_t last, compare comp);
- template <class iter_t>
- void parallel_stable_sort (iter_t first, iter_t last, uint32_t num_thread);
- template <class iter_t, typename compare>
- void parallel_stable_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]
|