如何在 C++ 期间监控/显示进度种类

Question

我计划编写一个交互式 C++ 几何处理插件，该插件将经常对大量数据进行排序。尽管初步迹象表明排序只需要一两秒，但我更愿意在这段时间内显示进度 - 即我想每秒更新几次进度指示器。这比打开等待光标并使用户留下一个冻结不确定时间长度（即使只有几秒钟）的程序更好。

如果我要使用像 std::sort 这样的东西，我可以使用比较函数时不时地更新进度指示器，但我不知道“完成百分比”。我还可以将排序分解为子排序，更新子排序之间的进度，然后合并。我最好的选择可能是编写自己的排序方法，尽管我不知道需要付出多少努力才能获得与 std::sort 一样好的性能（并确保正确性）。无论如何，该排序方法偶尔会向回调方法发送“完成百分比”。

我想知道其他人是否遇到并解决了这个问题 - 我希望标准库中可能有一种排序方法可以实现我想要的功能，或者是我没有想到的其他技术。

更新：感谢迄今为止的精彩回答。有一些非常好的建议，我将推迟选择已接受的答案，直到我有机会在即将进行的项目中测试这些想法。

更新 2：我完成了我的项目，结果证明这不是问题（至少对于客户而言）。由于他们将销售该软件，他们仍然可能会从客户那里得到反馈改变他们的想法）。选择一个可接受的答案很困难，因为有很多好的答案，但最终我选择的答案指向一篇关于合并排序的维基文章，该文章有一个非常令人回味的动画。因此，如果我需要继续这样做，这就是我会采取的第一个策略）。

Answer 1

我认为，即使您编写自己的排序，如果您希望进度指示器准确，您也必须进行大量仔细的测量。如果您只想要一个近似的进度指示器，那么您可以使用一些指标，例如“比较元素之间的平均距离”或“与快速排序的平均预期数量相比的比较次数”作为指标，并实现您已经提到的比较想法。

是的，我认为您不是一个十足的白痴，也不打算在每次比较时更新进度指示器。如果你这样做，你会花更多的时间来指示进度而不是排序。

例如，您通常期望进行快速排序的 n log2 n 操作。对涉及多少比较的分析比一般测量更详细并且更准确，但出于本示例的目的，我们仅进行假设。因此，您可以计算比较次数并报告 number_of_comparisons / (n log2 n) 作为您对进度的估计。

由于这只是一个平均指标，我会进行一些实验，看看您的估计偏离了多少，并加入一些模糊因素以使其与平均预期情况相符。您还可以有一个进度条，通过“我认为我将完成的工作”来表示不确定性。指示器和指示器后面的一些空格。

即使你使用自己的排序并想出一个看似更精确的度量，进度条仍然不会平滑更新，效果也会相似。您确定排序将花费多长时间的唯一方法是，如果您使用稍微慢一些但真正可预测的排序，在这种情况下，您可以根据元素数量预测排序将花费多长时间，或者使用非常快的排序排序在特定情况下的行为不太可预测，在这种情况下，没有真正的方法可以拥有完全准确的进度条。

子任务的可预测性和比较总数的可预测性密切相关。所以我真的不认为子任务比比较总数更好。

如果您想使用自己的排序并且可预测性是您的最高目标，请选择堆排序。它仍然是一个 O(n log2 n) 排序，并且接近于最小比较排序（至少我在阅读 Knuth 时记得是这样）。无论输入的数据集是什么，它都需要非常可预测的时间才能完成。它是较慢的 O(n log2 n) 排序之一，但仍然如此。

正如您的一位评论者所提到的，您可能正在解决一个实际上并不存在的问题。首先进行一些实验。不管这个问题有什么用处，它都是一个有趣的智力挑战。 :-)

Answer 2

由于 std::sort 是基于模板的，因此源应该在标头中可用。您可以复制它并插入进度回调。最大的问题是预测你距离完成有多近——大多数排序函数将基于快速排序，它并不总是进行相同数量的比较。

编写您自己的合并排序是可能的；该算法很简单，步骤数也明确定义。

Answer 3

我建议您使用第二个选项：使用 std::sort 或其他标准排序函数（如 qsort），并让比较器报告其进度。但不要在每次比较中都更新——这会慢得难以忍受——而是每（比如）100 毫秒更新一次。

Answer 4

我认为您的问题如下：

1. 您希望在单个连续过程中触发离散事件。
2. 这个细分只是为了告诉用户事情正在进行中。

我的建议是：

1. 使用类似 http://ajaxload.info/ 的加载图标，或者如果它不是基于 GUI 的环境，只需说明加载即可。由于事件持续时间不到 2 秒，因此这不会成为问题。如果等待时间超过 10 秒，则会挂断。

2. 编写自己的排序方法确实会带来很多线程安全问题，如果您的代码使用多线程或将来必然会这样做，这可能会导致问题。

3.另一个重要信息是，每次您想要排序时，您都应该考虑数据的无序程度，因此实际上您将测量存在的随机性程度，以及您可能需要执行的预期计算数量。您可以使用此信息作为需要多少交换的指示器，而这反过来又可以在您迭代排序时进行计数。玩转数据。

Answer 5

使用蛮力:)

int elem_num = raw_data.size();
int percentage_delta = 100/(elem_num/20);
int percentage = 0;
int i = 0;
std::multiset<Elem*> sorted_data(&compareElemFunc);
foreach(Elem& elem, raw_data)
{
    sorted_data.insert(&elem);
    if(i%20)
    {
        updateProgressBar(percentage);
        percentage += percentage_delta;
    }
    i++;
}
//now, your data is perfectly sorted, iterate through sorted_data

（如果您不想实现自己的 std::sort() 并且因为我缺乏完整的要求）

Answer 6

使用观察者模式在每个部分完成时向父级发信号。使用它和需要排序的元素总数，您可以实时更新进度条。

Answer 7

我不建议尝试破解 std::sort。这通常使用 introsort 实现，并且是一种非常快的 NLogN 操作。构建要排序的容器通常比排序数据更昂贵。

但是，如果您要实现进度条，我建议您将排序放在单独的线程中。通常，多线程应用程序比单线程应用程序更难编写和维护，但您可以采用不适合此进度条情况的方式来实现。您的应用程序仍然可以主要是单线程的，而不执行任何并发操作，除了此进度条和可能的一些事件处理以保持 UI 响应之外。当您准备好对数据进行排序时，只需启动另一个线程来执行此操作，并将主线程置于等待循环中，直到排序线程完成，在此期间休眠并升级进度条。

您可以将这种非侵入式方法推广到任何类型的耗时操作，而不必在整个代码中散布 update_progress_bar() 类型调用或深入研究 std::sort 的实现或尝试重新发明轮子。由于主线程将处于等待/更新进度条状态，因此在某种意义上会阻塞，直到您的工作线程完成为止，因此您不会遇到与多线程相关的任何问题（需要线程同步来访问整个进程中的共享资源）应用程序（进度计数器、竞争条件、死锁等除外）。它也将是您可以实现的最流畅的进度计数器，因为它将同时更新。

如果您担心与锁定进度计数器相关的效率，只需使用原子操作来递增它。

至于确定排序算法的进展程度，有几种方法可以实现。一种是让它根据您拥有的数据大小运行一次，并尝试预测后续运行所需的时间。这是完全非侵入性的，但有点难以做到，但是，如果做得正确，它将比定期增加计数器更准确地监控进度（这忽略了间隔可能不会花费甚至大量时间的事实）。第二种方法更简单，但有点邪恶，是修改比较器谓词以增加进度计数器。使用状态进行谓词通常会令人不悦，但这比仅仅因为想要一个进度计数器而尝试实现自己的内部排序要好得多。

另外，如果你的 introsort 花了这么长时间，我不得不想知道，你的容器是否存储这些三角形对象或指向它们的指针？如果是前者，您可能需要考虑后者，因为它会大大加快速度。