如何计算排序时的“进度”？

Question

我使用stable_sort对一个大的vector进行排序。

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

但是(即使我要写自己的排序例程)我怎么知道我已经取得了多大的进步，还有多少工作要做呢？

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

Answer 1

将向量分成几个相等的部分，数量取决于您所需的进度报告粒度。分别对每个部分进行排序。然后开始与std::merge合并。您可以在对每个部分进行排序和每次合并后报告进度。您需要进行实验，以确定与合并相比，对部分的排序应该计算多少百分比。

编辑：

我自己做了一些实验，发现与排序相比，合并是微不足道的，这是我想出的函数：

template<typename It, typename Comp, typename Reporter>
void ReportSort(It ibegin, It iend, Comp cmp, Reporter report, double range_low=0.0, double range_high=1.0)
{
    double range_span = range_high - range_low;
    double range_mid = range_low + range_span/2.0;
    using namespace std;
    auto size = iend - ibegin;
    if (size < 32768) {
       stable_sort(ibegin,iend,cmp);        
    } else {
        ReportSort(ibegin,ibegin+size/2,cmp,report,range_low,range_mid);
        report(range_mid);
        ReportSort(ibegin+size/2,iend,cmp,report,range_mid,range_high);
        inplace_merge(ibegin, ibegin + size/2, iend);
    }   
}

int main()
{
    std::vector<int> v(100000000);
    std::iota(v.begin(), v.end(), 0);
    std::random_shuffle(v.begin(), v.end());

    std::cout << "starting...\n";

    double percent_done = 0.0;
    auto report = [&](double d) {
        if (d - percent_done >= 0.05) {
            percent_done += 0.05;
            std::cout << static_cast<int>(percent_done * 100) << "%\n";
        }
    };
    ReportSort(v.begin(), v.end(), std::less<int>(), report);
}

Answer 2

稳定排序是基于合并排序的。如果您编写了自己版本的合并排序(忽略一些加速技巧)，您将看到它由log N遍组成。每次遍历从2^k个排序列表开始，并生成2^(k-1)个列表，在将两个列表合并为一个列表时完成排序。因此，您可以使用k的值作为进度的指示。

如果您要运行实验，您可能会检测比较对象以计算进行的比较的数量，并尝试查看进行的比较的数量是否为n log n的某个合理的可预测倍数。然后，您可以通过计算完成的比较的数量来跟踪进度。

(请注意，对于C++稳定排序，您必须希望它找到足够的存储来保存数据的副本。否则，成本从N log N到N (log N)^2，您的预测将过于乐观)。

Answer 3

选择一小部分索引并计算反转次数。你知道它的最大值，并且你知道当你完成时，它的值是零。所以，你可以使用这个值作为“进度条”。你可以把它看作是熵的一种度量。