排序整个范围时,std :: partial_sort()与std :: sort()的性能如何？

Question

以下两种方法之间是否存在显着差异？方式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;
}

有些测试表明,如果必须对整个范围进行排序,则partial_sort明显更差(在我的用例中为4).这表明方式1是首选.似乎partial_sort仅用于排序整个范围的一小部分.我在Visual Studio 2010中测试过.

Answer 1

根据sgi doc,partial_sort使用heapsort,sort使用introsort:

partial_sort(first,last,last)具有排序整个范围[first,last]的效果,就像sort(first,last)一样.但是它们使用不同的算法:sort使用introsort算法(quicksort的变体),partial_sort使用heapsort.参见Knuth的第5.2.3节(DE Knuth,计算机程序设计的艺术.第3卷:排序和搜索.Addison-Wesley,1975.)和JWJ Williams(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
}