如何在C++排序过程中监控/显示进度

Question

如何在C++排序过程中监控/显示进度

9

我计划编写一个交互式的C++几何处理插件，需要频繁地对大量数据进行排序。虽然初步迹象表明排序只需要一两秒钟，但我更喜欢在此期间显示进度 - 即我想每隔几秒更新一次进度指示器。这比打开等待光标并让用户面对一个不确定时间冻结的程序要好（即使只有几秒钟）。

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

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

更新：感谢迄今为止提供的伟大答案。已经有一些非常好的建议，我将暂停选择接受的答案，直到我有机会在即将到来的项目中测试这些想法。

更新2：我完成了我的项目，这最终成为一个非问题（至少对于客户而言。由于他们将销售该软件，他们可能仍然会从客户那里得到反馈，这将改变他们的想法）。选择接受的答案很困难，因为有许多好的答案，但最终我选择的那个指向Merge Sort的wiki文章具有非常生动的动画效果。因此，如果我需要继续进行此操作，这是我将要追求的第一种策略。

- brainjam

3

个人建议在观察到实际排序性能之前，暂时不要添加这样的功能。否则就是解决一个可能不存在的问题。你也可以采用简单的方式，在某种日志文本控件或状态栏中显示“正在排序...”。 - Reinderien

1

@Reinderien：同意，如果它没有出现问题就不要修复它。但我正在尝试提前考虑这个问题。我的经验是，在3D图形和几何处理方面，用户很容易因为模型和数据太大而无法使用。 - brainjam

7个回答

4

由于std::sort基于模板，因此源代码应该在头文件中可用。您可以复制它并插入进度回调。最大的问题将是预测完成的接近程度-大多数排序函数将基于Quicksort，它不总是执行相同数量的比较。

编写自己的归并排序可能是一种可能性; 算法很简单，步骤数也很明确。

- Mark Ransom

两个好建议。我没有想到std::sort是基于模板的。供参考，rosettacode.org上有一个C++实现的归并排序：http://rosettacode.org/wiki/Merge_sort#C.2B.2B - brainjam

2

我建议您选择第二个选项：使用std::sort或其他标准排序函数，如qsort，并让比较器报告其进度。但不要在每次比较中更新--那将是无法忍受的慢--而是每隔（比如）100毫秒更新一次。

- JSBձոգչ

1

然而，这并没有回答原帖中的一个重要问题。使用这种方法，你如何实际确定排序已经完成了多少？ - Omnifarious

1

我认为如果您在构造函数中给比较器数组的大小，然后使用Omifarious上面的近似值（大约会有（n lg n）次比较），那么比较器就可以跟踪它被调用的次数。我不确定并且没有完全思考过，但我认为归并排序可能适合很好地跟踪进度。但是当然，归并排序不是内省排序。尽管如此，归并排序是（n lg n），可能是可以接受的。 - Craig Wright

@Craig W. Wright：这很困难，因为STL比较函数器不允许有状态。 - Billy ONeal

@Billy：怎么了？比较函数需要产生一致（时间不变）的结果，但据我所知，并没有禁止不改变返回值的副作用。 - Ben Voigt

@Ben：它本身并没有被禁止，但是算法允许通过按值传递的方式传递函数对象，这将导致您拥有一堆副本，每个都有单独的计数。为了得到一致的结果，您必须在函数对象之外存储信息（我猜您可以让函数对象存储一个指针...） - Billy ONeal

1

使用暴力破解 :)

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()，并且由于我缺乏完整的要求）

- Alsk

我认为这是O(n logn)，但我想知道它与使用std::sort相比如何。如果std::sort需要1秒钟，而这个解决方案需要10秒钟，我会再考虑一下是否使用它。这个解决方案的好处是你可以随时取消进程。顺便说一句，我会将进度更新因子从20更改为1000甚至10000——每秒几次更新就足够了。 - brainjam

1

我看到你的问题如下：

你希望在单个连续过程中触发离散事件。
这种子分区只是告诉用户事情正在进行中。

我的建议是：

使用来自http://ajaxload.info/之类的加载图标，或者如果不是基于GUI的环境，则只需拼写出加载。由于事件在2秒内完成，因此这不会成为问题。如果等待时间超过10秒，则预计会出现挂起。
编写自己的排序方法会带来许多线程安全问题，如果您的代码正在使用多线程或将来必须使用多线程，则可能会导致问题。

3.另一个重要信息是，每次想要排序时数据有多么乱，因此实际上您将测量存在的随机性程度以及可能需要执行的预期计算数量。您可以使用此信息作为指示器，以了解需要多少交换，这反过来可以在遍历排序时进行计数。尝试玩弄数据。

- Egon

0

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

- Konrad

0

我不建议尝试破解std::sort。通常情况下，它是使用introsort实现的，是一种极快的NLogN操作。构造要排序的容器通常比对数据进行排序更昂贵。

然而，如果你要实现一个进度条，我建议你将排序放在单独的线程中。通常，多线程应用程序比单线程应用程序更难编写和维护，但你可以以一种方式来完成这个进度条案例，使其不会变得更加困难。你的应用程序仍然可以主要是单线程的，除了这个进度条和可能需要保持UI响应的一些事件处理之外，没有任何并发操作被执行。当你准备好对数据进行排序时，只需启动另一个线程来执行它，并将主线程置于等待循环中，直到排序线程完成，在此期间睡眠并更新进度条。

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

如果您担心锁定进度计数器所带来的效率问题，只需使用原子操作进行递增即可。

关于确定排序算法的进展情况，有几种方法可以实现。其中之一是使用你所拥有数据的大小来运行一次，并尝试预测后续运行所需的时间量。这是完全非侵入性的，但有点难以做到，但如果做得正确，它将比定期间隔增加计数器（忽略了间隔可能不占用相同的时间）更准确地监控进度。第二种方法更简单但有点邪恶，就是修改你的比较器谓词来增加进度计数器。带有状态的谓词通常不受欢迎，但它比尝试实现自己的introsort要好，只因为你想要一个进度计数器。

此外，如果你的introsort花费太长时间，我不得不怀疑，你的容器是存储这些三角形对象还是指向它们的指针？如果是前者，你可能要考虑后者，因为它应该能大大加快速度。

- stinky472

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Omnifarious · Accepted Answer

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

是的，我假设您并不是完全的白痴，并且不计划在每一次比较时都更新进度指示器。如果你这样做了，你将花费比排序更多的时间来指示进度。

例如，对于快速排序，通常会预计需要约nlog2n个操作。虽然有关涉及的比较次数的分析可能更详细，也可能更准确，但为了本例的目的，让我们假设。因此，你可以计算比较次数，并报告number_of_comparisons / (n log2 n)作为进度的估计。

由于这只是一个平均指标，我建议运行一些实验，看看你的估计有多少偏差，并添加一些调整因素，使其与平均预期情况相吻合。你还可以通过在指示器后面添加一些空间来表示不确定性，从而具有进度条。

即使你使用自己的排序算法并得出了一个似乎更精确的度量标准，进度条仍然不会平滑更新，效果将是相似的。你唯一可以确切知道排序需要多长时间的方法是使用某种较慢但非常可预测的排序方法，在这种情况下，你可以根据元素数量预测需要多长时间，或者使用一个非常快速的排序方法，在特定情况下的行为不那么可预测，这种情况下没有真正的方法可以拥有完全准确的进度条。

子任务的可预测性和总比较次数的可预测性密切相关。因此，我认为子任务不比总比较次数更好作为衡量标准。

如果您想使用自己的排序算法，并且可预测性是您的最高目标，请选择堆排序。它仍然是一个O(n log2 n)排序，而且它接近于是一个最小比较排序（据我从Knuth的阅读中所记得）。无论它处理的数据集如何，它都需要非常可预测的完成时间。它是速度较慢的O(n log2 n)排序之一，但仍然不错。

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