std::stable_sort: 如何选择内存优化算法而不是时间优化算法？

Question

我想使用std::stable_sort。算法的复杂度表示为

O(N·log^2(N)), where N = std::distance(first, last) applications of cmp. If additional memory is available, then the complexity is O(N·log(N)). http://en.cppreference.com/w/cpp/algorithm/stable_sort

在我的应用程序中，内存很重要，因此，我更愿意std::stable_sort使用内存优化的 O(N·log^2(N)) 算法，而不是时间优化的 O(N·log(N)) 算法。我了解只有在安全的情况下才会选择时间优化版本这样做（内存可用）。但是，我的目标是对我的应用程序进行基准测试，因此，由于内存至关重要，因此我希望在内存消耗最低时对算法进行基准测试。因为我的系统目前有足够的内存来分配缓冲区，它将自动选择 std::stable_sort 的 O(N·log^2(N)) 版本。因此，我想断言 std::stable_sort 到采用内存优化版本。这可能吗？

执行政策出现是可以修改算法的参数，但是，它出现只改变并行度。 http://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t

尽管选择并行或顺序版本实际上可能正在选择 O(N·log(N)) 或分别是O(N·log^2(N))个版本，这个网页上没有说明。

不知道有没有人有断言这个选择的经验。如果是这样他们能提供什么建议吗？

Answer 1

您可以查看 headers 并查看在额外缓冲区不可用时调用了哪个函数。对我来说，在 gcc 上是

    std::__inplace_stable_sort(__first, __last, __comp);

这当然不符合标准。 __inplace_stable_sort 是辅助函数，不能直接使用。

std::stable_sort调用此函数是以下代码的结果

typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
  _TmpBuf __buf(__first, __last);

  if (__buf.begin() == 0)
std::__inplace_stable_sort(__first, __last, __comp);
  else
std::__stable_sort_adaptive(__first, __last, __buf.begin(),
                _DistanceType(__buf.size()), __comp);

Answer 2

遗憾的是，没有标准方法告诉 stable_sort 进行就地排序。在 C++14 中，我们只有

template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

C++17 添加了允许您指出的执行策略的版本，但这些版本也不会影响决策。如果我们查看 [[=25=]] 中的复杂性要求，我们会得到

Complexity: It does at most N log²(N) (where N == last - first) comparisons; if enough extra memory is available, it is N log(N).

因此，如果可用，则必须使用更多内存。

您要么必须自己编写并且可以查看 Worst case O(nlnn)O(nln⁡n) in place stable sort?，要么找到一个为您提供该功能的库。

std::stable_sort: 如何选择内存优化算法而不是时间优化算法？

std::stable_sort: How to choose memory-optimised algorithm over time-optimised algorithm?

c++

sorting

std

c++17

stable-sort