EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 09:51:48
0001 //Templated Spreadsort-based implementation of integer_sort 0002 0003 // Copyright Steven J. Ross 2001 - 2014. 0004 // Distributed under the Boost Software License, Version 1.0. 0005 // (See accompanying file LICENSE_1_0.txt or copy at 0006 // http://www.boost.org/LICENSE_1_0.txt) 0007 0008 // See http://www.boost.org/libs/sort/ for library home page. 0009 0010 /* 0011 Some improvements suggested by: 0012 Phil Endecott and Frank Gennari 0013 0014 Doxygen comments by Paul A. Bristow Jan 2015 0015 0016 */ 0017 0018 #ifndef BOOST_INTEGER_SORT_HPP 0019 #define BOOST_INTEGER_SORT_HPP 0020 #include <algorithm> 0021 #include <vector> 0022 #include <cstring> 0023 #include <limits> 0024 #include <boost/static_assert.hpp> 0025 #include <boost/sort/spreadsort/detail/constants.hpp> 0026 #include <boost/sort/spreadsort/detail/integer_sort.hpp> 0027 #include <boost/range/begin.hpp> 0028 #include <boost/range/end.hpp> 0029 0030 namespace boost { 0031 namespace sort { 0032 namespace spreadsort { 0033 //Top-level sorting call for integers. 0034 0035 0036 /*! \brief Integer sort algorithm using random access iterators. 0037 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). 0038 0039 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, 0040 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n 0041 Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, 0042 so @c integer_sort is asymptotically faster 0043 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, 0044 so its worst-case with default settings for 32-bit integers is 0045 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n 0046 Some performance plots of runtime vs. n and log(range) are provided:\n 0047 <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> 0048 \n 0049 <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> 0050 0051 \param[in] first Iterator pointer to first element. 0052 \param[in] last Iterator pointing to one beyond the end of data. 0053 0054 \pre [@c first, @c last) is a valid range. 0055 \pre @c RandomAccessIter @c value_type is mutable. 0056 \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> 0057 \pre @c RandomAccessIter @c value_type supports the @c operator>>, 0058 which returns an integer-type right-shifted a specified number of bits. 0059 \post The elements in the range [@c first, @c last) are sorted in ascending order. 0060 0061 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), 0062 the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw. 0063 0064 \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. 0065 \warning Invalid arguments cause undefined behaviour. 0066 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, 0067 enabling faster generic-programming. 0068 0069 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: 0070 \remark * N is @c last - @c first, 0071 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), 0072 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). 0073 0074 */ 0075 template <class RandomAccessIter> 0076 inline void integer_sort(RandomAccessIter first, RandomAccessIter last) 0077 { 0078 // Don't sort if it's too small to optimize. 0079 if (last - first < detail::min_sort_size) 0080 boost::sort::pdqsort(first, last); 0081 else 0082 detail::integer_sort(first, last, *first >> 0); 0083 } 0084 0085 /*! \brief Integer sort algorithm using range. 0086 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). 0087 0088 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, 0089 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n 0090 Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, 0091 so @c integer_sort is asymptotically faster 0092 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, 0093 so its worst-case with default settings for 32-bit integers is 0094 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n 0095 Some performance plots of runtime vs. n and log(range) are provided:\n 0096 <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> 0097 \n 0098 <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> 0099 0100 \param[in] range Range [first, last) for sorting. 0101 0102 \pre [@c first, @c last) is a valid range. 0103 \post The elements in the range [@c first, @c last) are sorted in ascending order. 0104 0105 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), 0106 the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw. 0107 0108 \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. 0109 \warning Invalid arguments cause undefined behaviour. 0110 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, 0111 enabling faster generic-programming. 0112 0113 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: 0114 \remark * N is @c last - @c first, 0115 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), 0116 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). 0117 0118 */ 0119 template <class Range> 0120 inline void integer_sort(Range& range) 0121 { 0122 integer_sort(boost::begin(range), boost::end(range)); 0123 } 0124 0125 /*! \brief Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator. 0126 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). 0127 0128 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, 0129 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n 0130 Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, 0131 so @c integer_sort is asymptotically faster 0132 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, 0133 so its worst-case with default settings for 32-bit integers is 0134 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n 0135 Some performance plots of runtime vs. n and log(range) are provided:\n 0136 <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> 0137 \n 0138 <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> 0139 0140 \param[in] first Iterator pointer to first element. 0141 \param[in] last Iterator pointing to one beyond the end of data. 0142 \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits. 0143 \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. 0144 0145 \pre [@c first, @c last) is a valid range. 0146 \pre @c RandomAccessIter @c value_type is mutable. 0147 \post The elements in the range [@c first, @c last) are sorted in ascending order. 0148 0149 \return @c void. 0150 0151 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), 0152 the right shift, subtraction of right-shifted elements, functors, 0153 or any operations on iterators throw. 0154 0155 \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. 0156 \warning Invalid arguments cause undefined behaviour. 0157 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, 0158 enabling faster generic-programming. 0159 0160 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: 0161 \remark * N is @c last - @c first, 0162 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), 0163 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). 0164 */ 0165 template <class RandomAccessIter, class Right_shift, class Compare> 0166 inline void integer_sort(RandomAccessIter first, RandomAccessIter last, 0167 Right_shift shift, Compare comp) { 0168 if (last - first < detail::min_sort_size) 0169 boost::sort::pdqsort(first, last, comp); 0170 else 0171 detail::integer_sort(first, last, shift(*first, 0), shift, comp); 0172 } 0173 0174 /*! \brief Integer sort algorithm using range with both right-shift and user-defined comparison operator. 0175 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). 0176 0177 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, 0178 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n 0179 Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, 0180 so @c integer_sort is asymptotically faster 0181 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, 0182 so its worst-case with default settings for 32-bit integers is 0183 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n 0184 Some performance plots of runtime vs. n and log(range) are provided:\n 0185 <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> 0186 \n 0187 <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> 0188 0189 \param[in] range Range [first, last) for sorting. 0190 \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits. 0191 \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. 0192 0193 \pre [@c first, @c last) is a valid range. 0194 \post The elements in the range [@c first, @c last) are sorted in ascending order. 0195 0196 \return @c void. 0197 0198 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), 0199 the right shift, subtraction of right-shifted elements, functors, 0200 or any operations on iterators throw. 0201 0202 \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. 0203 \warning Invalid arguments cause undefined behaviour. 0204 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, 0205 enabling faster generic-programming. 0206 0207 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: 0208 \remark * N is @c last - @c first, 0209 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), 0210 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). 0211 */ 0212 template <class Range, class Right_shift, class Compare> 0213 inline void integer_sort(Range& range, Right_shift shift, Compare comp) 0214 { 0215 integer_sort(boost::begin(range), boost::end(range), shift, comp); 0216 } 0217 0218 /*! \brief Integer sort algorithm using random access iterators with just right-shift functor. 0219 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). 0220 0221 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, 0222 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n 0223 0224 \par Performance: 0225 Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, 0226 so @c integer_sort is asymptotically faster 0227 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, 0228 so its worst-case with default settings for 32-bit integers is 0229 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n 0230 Some performance plots of runtime vs. n and log(range) are provided:\n 0231 * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n 0232 * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> 0233 0234 \param[in] first Iterator pointer to first element. 0235 \param[in] last Iterator pointing to one beyond the end of data. 0236 \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits. 0237 0238 \pre [@c first, @c last) is a valid range. 0239 \pre @c RandomAccessIter @c value_type is mutable. 0240 \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> 0241 \post The elements in the range [@c first, @c last) are sorted in ascending order. 0242 0243 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), 0244 the right shift, subtraction of right-shifted elements, functors, 0245 or any operations on iterators throw. 0246 0247 \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. 0248 \warning Invalid arguments cause undefined behaviour. 0249 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, 0250 enabling faster generic-programming. 0251 0252 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: 0253 \remark * N is @c last - @c first, 0254 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), 0255 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). 0256 0257 */ 0258 template <class RandomAccessIter, class Right_shift> 0259 inline void integer_sort(RandomAccessIter first, RandomAccessIter last, 0260 Right_shift shift) { 0261 if (last - first < detail::min_sort_size) 0262 boost::sort::pdqsort(first, last); 0263 else 0264 detail::integer_sort(first, last, shift(*first, 0), shift); 0265 } 0266 0267 0268 /*! \brief Integer sort algorithm using range with just right-shift functor. 0269 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). 0270 0271 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, 0272 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n 0273 0274 \par Performance: 0275 Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, 0276 so @c integer_sort is asymptotically faster 0277 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, 0278 so its worst-case with default settings for 32-bit integers is 0279 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n 0280 Some performance plots of runtime vs. n and log(range) are provided:\n 0281 * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n 0282 * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> 0283 0284 \param[in] range Range [first, last) for sorting. 0285 \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits. 0286 0287 \pre [@c first, @c last) is a valid range. 0288 \post The elements in the range [@c first, @c last) are sorted in ascending order. 0289 0290 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), 0291 the right shift, subtraction of right-shifted elements, functors, 0292 or any operations on iterators throw. 0293 0294 \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. 0295 \warning Invalid arguments cause undefined behaviour. 0296 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, 0297 enabling faster generic-programming. 0298 0299 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: 0300 \remark * N is @c last - @c first, 0301 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), 0302 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). 0303 0304 */ 0305 template <class Range, class Right_shift> 0306 inline void integer_sort(Range& range, Right_shift shift) 0307 { 0308 integer_sort(boost::begin(range), boost::end(range), shift); 0309 } 0310 } 0311 } 0312 } 0313 0314 #endif 0315
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|