Производительность std ::part_sort () по сравнению с std :: sort () при сортировке всего диапазона?

Question

Производительность std ::part_sort () по сравнению с std :: sort () при сортировке всего диапазона?

Есть ли существенная разница между следующими двумя подходами? Способ 1 использует sort или же partial_sortв зависимости от размера вектора, в то время как путь 2 всегда использует partial_sort, Я считаю способ 2 более привлекательным, потому что мой предикат немного сложнее, чем в примере, поэтому я не хочу его повторять. Но мне интересно, если partial_sort работает хуже чем sort потому что он не предназначен для сортировки всего диапазона, поэтому я склонен использовать способ 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;
}

Некоторое тестирование привело к тому, чтоpartal_Sort значительно хуже (в моем случае, в 4 раза), чем sort, если он должен сортировать весь диапазон. Это указывает на то, что способ 1 должен быть предпочтительным. Кажется, что part_sort предназначен только для сортировки небольшой части всего диапазона. Я тестировал в Visual Studio 2010.

5

c++partial-sort performance sorting

Решение

Другие решения

Ничто не требует, чтобы частичная_сортировка была реализована определенным образом, кроме гарантий сложности

25.4.1.3 part_sort [part.sort]

шаблон voidpartal_sort (сначала RandomAccessIterator,
RandomAccessIterator середина, RandomAccessIterator последний);
шаблон
voidpartal_sort (сначала RandomAccessIterator, середина RandomAccessIterator,
RandomAccessIterator последний, Сравнить комп);

1 Эффекты: помещает первые середины — первые отсортированные элементы из диапазона [first, last) в диапазон [first, middle). Остальные элементы в диапазоне [middle, last) расположены в неуказанном порядке.

2 Требуется:
RandomAccessIterator должен удовлетворять требованиям ValueSwappable
(17.6.3.2). Тип * first должен удовлетворять требованиям
MoveConstructible (Таблица 20) и MoveAssignable (Таблица 22).

3 Сложность: требуется приблизительно (последнее — первое) * log (среднее — первое) сравнение

Альтернативная реализация может быть

std::nth_element - average linear time
followed by
std::sort - on the reduced range begin()-nth (n log n)

1

Источник

Accepted Answer

В соответствии с Sgi Doc, partial_sort использования пирамидальная сортировка, sort использования introsort:

частичная_сортировка (первая, последняя, последняя) имеет эффект сортировки всего диапазона [первая, последняя), так же как сортировка (первая, последняя). Однако они используют разные алгоритмы: сортировка использует алгоритм внутренней сортировки (вариант быстрой сортировки), а частичная_сортировка использует heapsort. См. Раздел 5.2.3 Кнута (Д. Е. Кнут, Искусство компьютерного программирования. Том 3: Сортировка и поиск. Аддисон-Уэсли, 1975 г.) и Дж. У. Дж. Уильямса (CACM 7, 347, 1964). И heapsort, и introsort имеют сложность порядка N log (N), но, как правило, introsort выполняется быстрее в 2-5 раз.

Итак, это нормально partial_sort в 4 раза медленнее, чем sort,

Я проверил свою библиотеку VS2017 и нашел реализацию partial_sort а также sort, И это похоже на 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);
}

Сортировать

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
}

4