如何在C++排序中监视/显示进度

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

写你自己的 Merge sort 这是一种可能性;算法简单,步骤定义明确。

我认为,即使你写了自己的类型,如果你希望进度指示器是准确的,你也必须做很多仔细的测量。如果您只需要一个大致的进度指标,那么您可以使用一些指标,例如“比较元素之间的平均距离”或“与快速排序的平均预期数量相比的比较数量”,作为您的指标,并实现您已经提到的比较概念。

是的,我假设你不是一个完全的白痴,不打算在每次比较时更新进度指标。如果你这样做了,你会花更多的时间来指示进度,而不是排序。

作为一个例子,您通常希望 n log2 n 快速排序操作。对所涉及的比较数量的分析比一般的度量更详细,也更准确,但就本例而言,让我们假设一下。所以你可以计算比较和报告 number_of_comparisons / (n log2 n) 作为你对进展的估计。

因为这只是一个平均指标,所以我会做一些实验,看看你的估计偏离了多远,再加上一些捏造的因素,使之与平均预期情况一致。你也可以有一个进度条,它通过“这是我想我要做的地方”来表示不确定性,指示器和指示器后面的一些空格。

即使您使用自己的类型并提出了一个看起来更精确的度量,进度条仍然不会顺利更新,效果也会类似。你唯一能确定你的排序需要多长时间的方法是,如果你使用一个稍微慢一点但真正可预测的排序,在这种情况下,你可以从元素的数量来预测它需要多长时间,或者使用一个在特定情况下具有不太可预测行为的非常快的排序,在这种情况下,没有真正的方法能够完全准确地进行排序。速率进度条。

子任务的可预测性和总比较数的可预测性有很强的联系。所以我真的不认为子任务比总的比较数量更好。

如果你想使用你自己的类型和可预测性是你的最高目标,去 heapsort . 它仍然是一个 O(n log2 n) 排序,这接近于一个最小比较排序(我记得从阅读Knuth)。不管数据集的输入是什么,它都需要很长的时间来完成。它是最慢的 O(n Log2 n) 可以,但仍然可以。

正如你的一位评论者所提到的,你可能正在解决一个实际上并不存在的问题。先做些实验。然而,这个问题是一个有趣的智力挑战,不管它是否有用。-)

我建议你第二种选择:使用 std::sort 或者另一个标准的排序功能 qsort 并让比较器报告其进度。但不要在每次比较中都更新——那会是 难以忍受地 慢——而是每隔100毫秒更新一次。

我认为你的问题如下:

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

我的建议是:

1. 使用类似的加载图标 http://ajaxload.info/ 或者如果它不是基于图形用户界面的环境,只需详细说明加载。由于事件低于2秒,因此这不是问题。如果等待时间超过10秒,则需要挂断。

2. 编写自己的排序方法确实会带来许多线程安全问题,如果您的代码正在使用多线程或者将来一定要使用多线程,那么这可能会导致问题。

3.另一个重要的信息是,您应该考虑每次排序时数据的无序程度,因此实际上,您将测量当前的随机性程度以及可能需要进行的预期计算数量。您可以将此信息用作指示需要多少交换的指标,而在遍历排序时,这些交换又可以作为计数。玩弄数据。

使用暴力:)

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(),并且因为我缺少完整的需求)

使用 observer pattern 当每个部分完成时向父级发出信号。使用它和需要排序的元素总数,您可以实时更新进度条。

我不建议尝试破解std::sort。这通常是用IntroSort实现的,是一种非常快速的非登录操作。构建要排序的容器通常比对数据进行排序更昂贵。

但是,如果您要实现一个进度条,我建议您将排序放在一个单独的线程中。通常情况下,多线程应用程序比单线程应用程序更难编写和维护,但您可以用一种不适合此进度条的方式来完成。您的应用程序仍然可以主要是单线程的,不需要执行任何并发操作,除了这个进度条和一些事件处理来保持UI的响应性。当您准备好对数据进行排序时,只需启动另一个线程来执行该操作,并将主线程放入等待循环,直到排序线程完成为止,在这里和那里睡觉,同时升级进度条。

您可以将这种非侵入式方法推广到任何类型的耗时操作中,而无需在代码中撒上更新进度条()类型调用,或深入研究std::sort的实现,或尝试重新设计轮子。由于主线程将处于等待/更新进度条状态,因此在工作线程完成之前在某种意义上是阻塞的,因此您没有任何与多线程相关的问题(需要线程同步以访问整个应用程序中的共享资源,但进度计数器除外,race co条件、死锁等)。它也是可以实现的最平滑的进度计数器,因为它将同时更新。

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

至于确定排序算法进展了多少,有两种方法可以做到这一点。一种是让它以您拥有的数据大小运行一次,并尝试预测后续运行所需的时间。这是完全非侵入性的,但有点难做,但是,如果做得正确,它将比定期递增计数器更准确地监控进度(这忽略了间隔可能不会花费大量时间的事实)。第二种方法更简单,但有点邪恶,就是修改comparator谓词以增加进度计数器。使用状态来创建谓词通常是不受欢迎的,但这并不比仅仅因为需要一个进度计数器而尝试实现自己的introsort那么糟糕。

另外,如果您的introsort花费了这么长的时间,我想知道,您的容器是否存储了这些三角形对象或指向它们的指针?如果是前者,您可能会考虑后者,因为它会显著加快速度。