我希望使用 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)) 个版本,网页上没有说明。
我想知道是否有人有任何主张这种选择的经验。如果是这样 他们能提供任何建议吗?
最佳答案
您可以查看您的 header ,看看如果额外的缓冲区不可用,则调用哪个函数。对我来说 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);
关于c++ - std::stable_sort:如何选择内存优化算法而不是时间优化算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44947510/