我希望使用std::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))版本,这在网页上没有任何说明。
我想知道是否有人在主张这一选择方面有任何经验。如果是这样
他们能够提供任何建议吗?
最佳答案
您可以查看标题,看看如果没有额外的缓冲区,哪个函数会被调用。对我来说,这是
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);