std :: stable_sort:如何在时间优化算法中选择内存优化算法？

Question

我想利用std::stable_sort.算法的复杂性表示为

O(N·log ^ 2(N)),其中N = std :: distance(first,last)cmp的应用.如果有额外的内存,则复杂度为O(N·log(N)).http://en.cppreference.com/w/cpp/algorithm/stable_sort

在我的申请中,存储器是至关重要的,因此,我宁愿std::stable_sort使用存储器优化的O(N·登录^ 2(N))的算法,而不是时间优化O(N·日志(N))的算法.我知道只有在安全的情况下才会选择时间优化版本(可用内存).但是,我的目标是对我的应用程序进行基准测试,因此,当内存非常重要时,需要在内存消耗最低时对算法进行基准测试.由于我的系统目前有足够的内存来分配缓冲区,它会自动选择O(N·log ^ 2(N))版本std::stable_sort.因此,我想主张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

如果额外的缓冲区不可用,您可以查看标题并查看调用哪个函数.对我来说,这是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添加了允许执行策略的版本,但是这些版本也不会影响决策.如果我们看一下[stable.sort]中的复杂性要求,我们就会得到

复杂性:它最多N log²(N)(在哪里N == last - first)进行比较; 如果有足够的额外内存可用,那就是N log(N).

因此,如果可用,则强制使用更多内存.

你要么将不得不写自己的,你可以看到最坏情况O(ñ LN ñ)O(ñ ln⁡ ñ)代替稳定的排序？关于那个或找到一个为您提供功能的库.