SPW*_*ley 72 language-agnostic algorithm user-interface
在许多应用程序中,我们为文件下载,压缩任务,搜索等提供了一些进度条.我们经常使用进度条让用户知道正在发生的事情.如果我们知道一些细节,例如已完成了多少工作以及剩下多少工作,我们甚至可以通过推断从达到当前进度水平所需的时间来估算时间.
压缩ETA截图http://jameslao.com/wp-content/uploads/2008/01/winrar-progress-bar.png
但我们也看到这个时间留下"ETA"显示的程序只是滑稽的坏.它声称文件副本将在20秒内完成,然后一秒后它会说需要4天,然后再次闪烁20分钟.它不仅无益,而且令人困惑!ETA变化如此之大的原因是进度本身可能会有所不同,程序员的数学运算可能过于敏感.
苹果公司通过避免任何准确的预测并仅仅给出模糊估计来回避这一点! Apple的模糊逃避http://download.autodesk.com/esd/mudbox/help2009/images/MED/DaliSP1/English/Install_licensing/install_progress_MAC.png
这也很烦人,我有时间快速休息,还是我的任务将在2秒内完成？如果预测太模糊,那么完全做出任何预测毫无意义.
简单但错误的方法
作为第一次通过ETA计算,可能我们都只是做一个函数,如果p是已经完成的小数百分比,t是到目前为止所用的时间,我们输出t*(1-p)/ p作为估计完成需要多长时间.这个简单的比例可以"正常",但它也很糟糕,特别是在计算结束时.如果你的缓慢下载速度让副本慢慢地在一夜之间发生,最后在早上,一些东西开始运行,副本开始全速前进,速度提高了100倍,你完成90%的ETA可能会说"1小时",10秒之后你会达到95%而且ETA会说"30分钟",这显然是一个令人难以置信的糟糕猜测.在这种情况下,"10秒"是一个非常好的估计.
当发生这种情况时,您可能会考虑更改计算以使用最近的速度而不是平均速度来估算ETA.您可以获取过去10秒内的平均下载速率或完成率,并使用该速率来预测完成时间.这在之前的一夜之间下载过程中表现相当不错,因为它将在最后给出非常好的最终完成估算.但是这仍然存在很大问题..当你的速率在很短的时间内快速变化时,它会导致你的ETA大幅反弹,你会得到"在20秒内完成,在2小时内完成,在2秒内完成,在30秒内完成"分钟"快速显示编程耻辱.
实际问题:
在给定计算的时间历史的情况下,计算任务完成的估计时间的最佳方法是什么？我不是在寻找GUI工具包或Qt库的链接.我问的算法是生成最理智和准确的完成时间估计.
你有数学公式的成功吗？某种平均值,可能是使用超过10秒的速率平均值,速率超过1分钟,速率超过1小时？某种人工过滤,例如"如果我的新估计值与之前的估计值相差太大,请将其调低,不要让它反弹太多"？某种奇特的历史分析,您可以将进度与时间进度相结合,找到速率的标准偏差,以便在完成时给出统计误差指标？
你尝试了什么,什么效果最好？
ily*_* n. 31
创建这个站点的公司显然是在一个员工编写代码的环境中创建一个能够回答这个问题的调度系统.它的工作方式是基于过去的蒙特卡罗模拟未来.
这就是该算法在您的情况下的工作方式:
您将任务建模为一系列微任务,比如1000个.假设一小时后你完成了100个.现在,您通过随机选择90个已完成的微任务,运行模拟剩下的900个步骤,添加它们的时间并乘以10.这里您有一个估计; 重复N次,你有剩余时间的N估计值.请注意,这些估计值之间的平均值约为9小时 - 这里没有任何意外.但是,通过向用户提供最终的分发,您将诚实地向他传达可能性,例如"概率为90%,这将需要另外3-15小时"
根据定义,如果所讨论的任务可以被建模为一堆独立的随机微任务,则该算法产生完整的结果.只有当您知道任务如何偏离此模型时,您才能获得更好的答案:例如,安装程序通常具有下载/解包/安装任务列表,并且一个人的速度无法预测另一个.
我不是统计大师,但我认为如果你仔细观察这种方法中的模拟,它总会将正态分布作为大量独立随机变量的总和.因此,您根本不需要执行它.事实上,你甚至不需要存储所有完成的时间,因为你只需要它们的总和和它们的平方和.
可能不是非常标准的表示法,
sigma = sqrt ( sum_of_times_squared-sum_of_times^2 )
scaling = 900/100 // that is (totalSteps - elapsedSteps) / elapsedSteps
lowerBound = sum_of_times*scaling - 3*sigma*sqrt(scaling)
upperBound = sum_of_times*scaling + 3*sigma*sqrt(scaling)
有了这个,您可以输出消息,说明事物将从现在开始以[lowerBound,upperBound]之间以一些固定的概率结束(应该是大约95%,但我可能错过了一些常数因素).
SPW*_*ley 14
这是我发现的效果很好!对于任务的前50%,您假设速率是恒定的并且推断.时间预测非常稳定,不会反弹太多.
一旦超过50%,就可以切换计算策略.你把剩下的工作的一小部分做(1-p),然后回顾你自己进步的历史,找到(通过二分搜索和线性插值)你花了多长时间去做(1-p) -p)百分比并将其用作您的时间估计完成时间.
所以,如果你现在完成了71%,你剩下29%.你回顾一下你的历史,并发现你多久以前(71-29 = 42%)完成.将时间报告为您的ETA.
这自然是适应性的.如果你有大量的工作要做,它只会看到完成X工作量所需的时间.当你完成99%时,它只使用非常新鲜的,非常近期的估计数据.
它当然不是完美的,但它会平滑地改变,并且在它最有用时最终会特别准确.
我通常使用指数移动平均线来计算平滑因子为0.1的操作速度,并使用它来计算剩余时间.这样,所有测量的速度都会对当前速度产生影响,但最近的测量结果比远处的测量结果有更大的影响.
在代码中它看起来像这样:
alpha = 0.1 # smoothing factor
...
speed = (speed * (1 - alpha)) + (currentSpeed * alpha)
如果您的任务规模统一,则currentSpeed只需执行上一个任务所需的时间.如果任务具有不同的大小并且您知道一个任务应该是i,e,是另一个任务的两倍,则可以将执行任务所花费的时间除以其相对大小以获得当前速度.使用speed您可以通过将剩余时间乘以剩余任务的总大小来计算剩余时间(如果任务是统一的,则只计算其数量).
希望我的解释很清楚,当天有点晚了.
虽然所有示例都是有效的,但对于"下载时间"的具体情况,我认为查看现有的开源项目以了解它们的作用是个好主意.
从我所看到的,Mozilla Firefox是估计剩余时间的最佳选择.
火狐浏览器
Firefox会跟踪剩余时间的最后估计值,并通过使用此值和当前剩余时间估计值来执行平滑功能.请在此处查看ETA代码.这将使用将预先计算值一个"速度" 在这里,是最后10个读数的平滑平均值.
这有点复杂,所以解释一下:
谷歌浏览器
Chrome似乎在各地跳了起来,代码显示了这一点.
我喜欢Chrome的一个方面是它们如何格式化剩余时间.> 1小时后说'剩下1小时'<1小时后说"剩下59分钟"<1分钟说'剩下5秒'
你可以在这里看到它的格式
的DownThemAll!经理
它没有使用任何聪明的东西,这意味着ETA会在整个地方跳跃.
请参阅此处的代码
pySmartDL(python下载器)
获取最近30次ETA计算的平均ETA.听起来像是一种合理的方式.
请参阅此处的代码/blob/916f2592db326241a2bf4d8f2e0719c58b71e385/pySmartDL/pySmartDL.py#L651)
传输
在大多数情况下提供相当好的ETA(除非在开始时,如预期的那样).
在过去的5个读数中使用平滑因子,类似于Firefox但不太复杂.从根本上类似于Gooli的答案.
请参阅此处的代码