8

以下两种方法之间是否存在显着差异？方式 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 比 sort 差得多（在我的用例中是 4 倍）。这表明方式 1 是首选。似乎 partial_sort 仅用于对整个范围的一小部分进行排序。我在 Visual Studio 2010 中进行了测试。

4

2 回答 2

8

根据sgi doc，partial_sort使用heapsort，sort使用introsort：

partial_sort(first, last, last) 具有对整个范围 [first, last) 进行排序的效果，就像 sort(first, last)。但是，它们使用不同的算法：sort 使用 introsort 算法（快速排序的一种变体），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 库，发现了 and 的partial_sort实现sort。它与 SGI 类似。

部分排序

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
}
于 2017-08-02T08:25:55.363 回答
1

除了保证复杂性外，没有什么要求以某种方式实现 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) 中的第一个中间元素 - 第一个排序的元素放入范围 [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)
于 2017-08-02T10:08:14.277 回答