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·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))版本，但网页上没有说明。

我想知道是否有人有选择的经验。如果有，他们能提供任何建议吗？

- izaak_pyzaak

---

阅读参考文献的注释部分，你就能得到答案。 - Some programmer dude

@Someprogrammerdude 我认为 OP 知道这一点，但希望能够在有可用空间的情况下选择 O(N log^2(N))（但我不完全确定为什么）。 - Thomas Russell

如果你无论如何都不在目标系统上运行基准测试，那么你的基准测试有多少用处？我认为与整体性能差异相比，这个问题只会产生较小的影响。 - 463035818_is_not_a_number

如果您具有这样的特定要求，也许您应该考虑将自己实现的排序算法集成到您的代码库中。 - moooeeeep

你可以使用WikiSort（因为强制std::stable_sort不使用内存是不可能的）代替它。它的默认C++实现可以在没有额外内存的情况下进行原地稳定排序，具有相当高的性能。如果你对内存有一定的控制权，还可以强制它使用固定大小的缓冲区，在避免动态内存分配的同时提高了性能。此外，flat_stable_sort也符合您的要求，并且可能会在某个时候被包含在Boost中。 - Morwenn

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);

- Captain Giraffe

---

这是我的建议，但请注意你正在进入充满龙的领域。这个功能在你的下一个编译器版本中不是必需的。 - Captain Giraffe

@izaak_pyzaak，这可能不足以满足您的基准测试需求，因为基准测试本身就是与实现相关的。假设您使用的是libstdc++。 - Arne Vogel

这个答案是正确的，但我想澄清一些可能会被误解的东西。std::__inplace_stable_sort(__first, __last, __comp); 完全符合标准。像这样的名称是为了让实现能够在不受(或干扰)外部人员影响的情况下使用它们而保留的。在代码中使用这些名称可能会导致不可预测的结果。 - Pete Becker

@izaak_pyzaak -- 不要让对龙的恐惧吓到你。试一试。如果它能工作，那就好了。如果你更换编译器后它不能工作，那么你就得找另一个解决方案。但这是最简单的方法。不要给自己增加额外的工作。 - Pete Becker

如果您使用此内容，必须 发表评论。否则，当它不可避免地出现故障时，维护者有权以杀意追究您的责任。解释这是什么以及为什么要这样做。 - Cody Gray

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)。

因此，如果有可用的更多内存，就必须使用更多的内存。

你要么需要编写自己的代码，关于此可以参考 Worst case O(n ln n) in place stable sort?)，或者找到一个提供该函数的库。

- NathanOliver

---

是的，那看起来就是共识。我想我得自己写了。干杯。 - izaak_pyzaak