bra*_*jam 8 c++ sorting algorithm progress-bar
我打算编写一个交互式C++几何处理插件,它经常对大量数据进行排序.虽然初步迹象表明排序只需要一两秒钟,但我更愿意在此期间显示进度 - 即我想每秒更新一次进度指示器几次.这比打开等待光标并让用户使用程序冻结一段不确定的时间(即使只是几秒钟)更可取.
如果我使用像std :: sort这样的东西,我可以使用比较函数来不时更新进度指示器,但我不知道'百分比完成'.我也可以将排序分解为子排序,更新子排序之间的进度,然后合并.我最好的选择可能是编写自己的排序方法,虽然我不知道需要多少努力才能获得与std :: sort一样好的性能(并确保正确性).在任何情况下,该排序方法偶尔会向回调方法发送"完成百分比".
我想知道其他人是否遇到并解决了这个问题 - 我希望在标准库中有一种排序方法可以实现我想要的,或者其他一些我没有想过的技术.
更新:感谢目前为止的最佳答案.有一些非常好的建议,在我有机会测试我即将开展的项目中的想法之前,我将暂缓选择已接受的答案.
更新2:我完成了我的项目,结果证明这是一个非问题(至少对于客户而言.由于他们将销售该软件,他们仍然可以从他们的客户那里获得反馈,这将改变他们对此的看法).选择一个接受的答案很难,因为有很多好的答案,但最后我选择的那个指向一个关于Merge Sort的wiki文章,它有一个非常令人回味的动画.所以,如果我需要继续这样做,这是我会追求的第一个策略).
我想,即使您自己编写了类型,如果您希望进度指示器准确,您也必须进行大量仔细测量.如果您只想要一个近似进度指示器,那么您可以使用某些指标,如"比较元素之间的平均距离"或"比较数量与快速排序的平均预期数量相比"作为您的指标,并实施您已经提到的比较想法.
是的,我认为你不是一个完全白痴,并且不打算在每次比较中更新进度指示器.如果你这样做,你会花费更多的时间来表明进展而不是排序.
例如,您通常会期望n log2 n快速排序的操作.涉及多少比较的分析更详细,并且可以比一般度量更准确,但是出于本示例的目的,我们假设.因此,您可以计算比较并报告number_of_comparisons / (n log2 n)您的进度估算.
由于这只是一个平均指标,我会进行一些实验,看看你的估计有多远,并投入一些软糖因素,使其与平均预期情况一致.你也可以有一个进度条,通过点击"这就是我认为我将要完成的地方"来表明不确定性.指标和指标后的一些空间.
即使您使用自己的排序并提出了更加看似精确的度量,进度条仍然无法顺利更新,效果也会类似.你知道你的排序要花多长时间的唯一方法就是使用一个稍微慢一点但实际上可预测的排序,在这种情况下你可以预测从元素数量中花费的时间,或者使用非常快的在特定情况下具有较少可预测行为的排序,在这种情况下,没有真正的方法来获得完全准确的进度条.
子任务的可预测性和总比较数的可预测性密切相关.所以我真的不认为子任务比总比较数更好.
如果您想使用自己的排序并且可预测性是您的最高目标,请选择heapsort.它仍然是O(n log2 n)一种类型,它接近于最小的比较排序(或者我记得从阅读Knuth).无论其喂食的数据集如何,它还需要非常可预测的时间来完成.这是速度较慢的一种O(n log2 n),但仍然存在.
正如您提到的一位评论者所说,您可能正在解决实际上并不存在的问题.先运行一些实验.然而,问题是一个有趣的智力挑战,无论其有用性如何.:-)