Executing std :: partial_sort () and std :: sort () when sorting the entire range?
Is there a significant difference between the following two approaches? Method 1 uses sort
or partial_sort
, depending on the size of the vector, while path 2 always uses partial_sort
. I find the way even more appealing because my predicate is a little more complex than the example, so I don't want to repeat it. But I'm wondering if it works any partial_sort
worse than sort
because it is not designed to sort the entire range, so I try to use method 1.
int main()
{
std::vector<double> vec;
vec.push_back(1.0);
vec.push_back(3.0);
vec.push_back(2.0);
vec.push_back(5.0);
vec.push_back(4.0);
vec.push_back(9.0);
const size_t numBest = 3;
const size_t numTotal= vec.size();
#if WAY1
if (numTotal < numBest)
{
std::sort(vec.begin(), vec.end(), std::not2(std::less<double>()));
}
else
{
std::partial_sort(vec.begin(), vec.begin() + numBest, vec.end(), std::not2(std::less<double>()));
vec.resize(numBest);
}
#elif WAY2
{
const size_t numMiddle = numTotal < numBest ? numTotal : numBest;
std::partial_sort(vec.begin(), vec.begin() + numMiddle, vec.end(), std::not2(std::less<double>()));
vec.resize(numMiddle);
}
#endif
// now vec contains the largest numBest results.
return 0;
}
In some tests it turned out that partial_sort is significantly worse (a factor of 4 in my usecase) than sort if the entire range needs to be sorted. This indicates that path 1 should be preferred. It seems that partial_sort is only meant to sort a small portion of the entire range. I have tested in Visual Studio 2010.
source to share
According to sgi doc , partial_sort
uses heapsort, sort
uses introsort:
partial_sort (first, last, last) has the effect of sorting the entire range [first, last), just like sort (first, last). However, they use different algorithms: sort uses introsort (a variant of quicksort) and partial_sort uses heapsort. See Section 5.2.3 of Knuth (D. E. Knuth, The Art of Programming, Volume 3: Sorting and Searching. Addison-Wesley, 1975.) and JWJ Williams (CACM 7, 347, 1964). Both the happort and introsort have complexity of the order of N log (N), but introsort is usually 2-5 times faster.
So that's ok partial_sort
4 times slower than sort
.
I checked my VS2017 library and found an implementation partial_sort
and sort
. And it looks like SGI.
partial_sort
template<class _RanIt,
class _Pr> inline
void _Partial_sort_unchecked(_RanIt _First, _RanIt _Mid, _RanIt _Last,
_Pr& _Pred)
{ // order [_First, _Last) up to _Mid, using _Pred
if (_First == _Mid)
return; // nothing to do, avoid violating _Pop_heap_hole_unchecked preconditions
_Make_heap_unchecked(_First, _Mid, _Pred);
for (_RanIt _Next = _Mid; _Next < _Last; ++_Next)
if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
{ // replace top with new largest
_Iter_value_t<_RanIt> _Val = _STD move(*_Next);
_Pop_heap_hole_unchecked(_First, _Mid, _Next, _STD move(_Val), _Pred);
}
_Sort_heap_unchecked(_First, _Mid, _Pred);
}
sort
template<class _RanIt,
class _Diff,
class _Pr> inline
void _Sort_unchecked1(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr& _Pred)
{ // order [_First, _Last), using _Pred
_Diff _Count;
while (_ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal)
{ // divide and conquer by quicksort
pair<_RanIt, _RanIt> _Mid =
_Partition_by_median_guess_unchecked(_First, _Last, _Pred);
_Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions
if (_Mid.first - _First < _Last - _Mid.second)
{ // loop on second half
_Sort_unchecked1(_First, _Mid.first, _Ideal, _Pred);
_First = _Mid.second;
}
else
{ // loop on first half
_Sort_unchecked1(_Mid.second, _Last, _Ideal, _Pred);
_Last = _Mid.first;
}
}
if (_ISORT_MAX < _Count)
{ // heap sort if too many divisions
_Make_heap_unchecked(_First, _Last, _Pred);
_Sort_heap_unchecked(_First, _Last, _Pred);
}
else if (2 <= _Count)
_Insertion_sort_unchecked(_First, _Last, _Pred); // small
}
source to share
Nothing requires partial_sort to execute in a specific way, except for guarantees of complexity
25.4.1.3 partial_sort [partial.sort]
template void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template void partial_sort (RandomAccessIterator first, RandomAccessIterator, RandomAccessIterator last, Compare comp);
1 Effects: puts the first mid-term sorted items from the range [first, last] into the range [first, middle]. The rest of the items in the range [middle, last] are placed in an unspecified order.
2 Required: RandomAccessIterator must meet the requirements of ValueSwappable (17.6.3.2). Type * must first satisfy the requirements of MoveConstructible (Table 20) and MoveAssignable (Table 22).
3 Complexity: Approximately required (last - first) * log (middle - first) comparisons
An alternative implementation could be
std::nth_element - average linear time
followed by
std::sort - on the reduced range begin()-nth (n log n)
source to share