c++ - 排序时如何找出 "progress"？

Question

我正在使用 stable_sort 对大型 vector 进行排序。

排序大约需要几秒钟(比如 5-10 秒)，我想向用户显示一个进度条，显示到目前为止完成了多少排序。

但是(即使我要编写自己的排序例程)我怎么知道我取得了多少进展，还有多少事情要做？

我不需要它是精确的，但我需要它是“合理的”(即合理的线性，没有伪造，当然也没有回溯)。

Answer 1

标准库排序使用用户提供的比较函数，因此您可以在其中插入一个比较计数器。 quicksort/introsort 或 mergesort 的比较总数将非常接近 log₂N * N(其中 N 是 vector 中的元素数)。这就是我要导出到进度条的内容:比较次数/N*log₂N

由于您使用的是合并排序，因此比较计数将是一种非常精确的进度度量。如果实现花时间在比较运行之间排列 vector ，它可能会稍微非线性，但我怀疑您的用户会看到非线性(无论如何，我们都习惯了不准确的非线性进度条 :))。

Quicksort/introsort 会显示更多方差，具体取决于数据的性质，但即使在那种情况下也总比没有好，您总是可以根据经验添加一个软糖因素。

您的比较类中的一个简单计数器几乎不会花费您任何费用。就我个人而言，我什至懒得加锁(加锁会影响性能)；它不太可能进入不一致的状态，而且进度条不会仅仅因为它获得不一致的进度数字而开始辐射蜥蜴。