std::partial_sort()和std::sort()在对整个范围进行排序时的性能比较？

Question

以下两种方法是否有重大差异？Way 1 根据向量的大小使用 sort 或 partial_sort，而 Way 2 总是使用 partial_sort。我发现 Way 2 更吸引人，因为我的谓词比示例中更复杂，所以我不想重复它。但我想知道 partial_sort 是否比 sort 执行得更差，因为它并不适用于对整个范围进行排序，这就是为什么我倾向于使用 Way 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倍），相比之下，sort更佳。这表明选择way 1更为合适。似乎partial_sort仅适用于对整个范围的一小部分进行排序。我在Visual Studio 2010中进行了测试。

- Fabian

---

1. 你不必重复谓词，只需将其存储在某个变量中即可。
2. 使用更简单、更易读的版本，如果速度较慢，则向编译器供应商投诉。
3. Visual Studio 2010并不是最近的版本...

- Marc Glisse

Answer 1

根据 sgi doc，partial_sort 使用堆排序(heapsort)，而sort使用 内省排序(introsort)：

partial_sort(first, last, last)的效果与sort(first, last)一样，都可以将范围[first, last)排序。但它们使用不同的算法：sort使用内省排序算法（快速排序的变体），而partial_sort使用堆排序。请参见Knuth（D. E. Knuth，计算机程序设计艺术，第3卷：排序和搜索。Addison-Wesley，1975年）的第5.2.3节，以及J.W.J. Williams（CACM 7,347,1964）。堆排序和内省排序的复杂度均为N log (N)，但内省排序通常比堆排序快2到5倍。

因此，partial_sort比sort慢4倍是正常的。

---

我已经检查了我的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
}

- delta

---

有趣 - 我想知道这是否在所有实现中都是真的。我记得有一个关于编译器之间排序性能差异的讲座。 - doctorlove

除了旧的SGI STL实现不一定与OP实现使用的标准库相同。 - juanchopanza

我觉得很奇怪，一个编译器供应商没有检查partial_sort（first，last，last）并在这种情况下使用sort。可能是他们想避免分支。 - Fabian

实际上，堆排序对于“partial_sort”来说是一个次优选择：它的内部循环大约比快速排序的内部循环长两倍，并且它的一半工作用于构建堆，其中包括整个范围内的所有元素。也就是说，堆排序基础的“partial_sort”所需的时间大约为(1 + n/N)*T，其中T是快速排序对整个范围进行排序所需的时间，n是输出范围的长度，N是输入范围的长度。最好直接使用快速排序对整个范围进行排序。 - cmaster - reinstate monica

SGI文档链接把我带到了HP网站？ - wcochran

Answer 2

除了复杂度的保证外，partial_sort没有特定的实现要求。

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 middle, RandomAccessIterator last, Compare comp);

1 效果：将范围 [first,last) 中前 middle - first 个排序的元素放入范围 [first,middle) 中。范围 [middle,last) 中的其余元素以未指定的顺序放置。

2 要求：RandomAccessIterator 必须满足 ValueSwappable（17.6.3.2）的要求。*first 的类型必须满足 MoveConstructible（Table 20）和 MoveAssignable（Table 22）的要求。

3 复杂度：它需要大约（last - first）* log(middle - first) 次比较。

另一种可能的实现方式是

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

- Surt

---

为什么你认为堆排序比这个替代方案更好？如果std::nth_element很快，似乎这会更简单。此外，这表明std::partial_sort不是正交的。 - wcochran

@wcochran 堆排序比内省排序慢，但如果您只想获取K个最高的排序，则堆排序会更快。有一个关于这个主题的cppcon(?)视频值得一看。 - Surt