智能进度条ETA计算
在许多应用程序中，我们有一些文件下载，压缩任务，search等进度条。我们都经常使用进度条来让用户知道正在发生的事情。 如果我们知道一些细节，比如已经完成了多less工作，还有多less工作要做，我们甚至可以给出一个时间估计，通常是从多less时间推断到达当前的进度水平。
压缩ETA截图http://jameslao.com/wp-content/uploads/2008/01/winrar-progress-bar.png
但是我们也看到了这个剩下时间“ETA”的节目只是非常糟糕。 它声称一个文件拷贝将在20秒内完成，然后一秒钟之后它说要花费4天，然后再闪烁20分钟。 这不仅无益，而且令人困惑！ ETA之所以变化如此之大，是因为进度本身可能会有所不同，程序员的math可能过于敏感。
苹果回避这个只是避免任何准确的预测，只是给模糊的估计！ 苹果的模糊回避http://download.autodesk.com/esd/mudbox/help2009http://img.dovov.comMED/DaliSP1/English/Install_licensing/install_progress_MAC.png
这也是烦人的，我是否有时间快速rest，还是我的任务要在2秒内完成？ 如果预测过于模糊，根本就没有任何预测。
简单但错误的方法
作为第一次ETA计算，可能我们都做了一个函数，如果p是已经完成的分数百分比，t是到目前为止的时间，我们输出t *（1-p）/ p作为需要多长时间才能完成。 这个简单的比例工作“OK”，但它也是可怕的，特别是在计算结束。 如果你的缓慢的下载速度让复制缓慢地前进，在一夜之间，最后在早上，一些东西开始，复制速度加快100倍，你完成90％的ETA可能会说“1小时”，10秒以后你在95％，ETA会说“30分钟”，这显然是一个不好的猜测..在这种情况下，“10秒”是一个更好的估计。
发生这种情况时，您可能会考虑将计算更改为使用最近的速度，而不是平均速度来估计ETA。 您在过去的10秒内获取平均下载速率或完成率，并使用该速率计算完成时间。 在之前的下载过程中，这个performance相当不错，因为它会在最后完成一个非常好的最终完成评估。 但是这仍然有很大的问题。当你的速度在很短的时间内迅速变化时，它会导致你的ETA反弹，你会得到“20秒完成，2小时完成，2秒完成，30完成分钟“快速显示编程的耻辱。
实际的问题是：
考虑到计算的时间历史，计算任务完成时间的最佳方法是什么？ 我不在寻findGUI工具包或Qt库的链接。 我在询问这个algorithm来产生最理智和准确的完成时间估计。
你有成功的math公式？ 某种平均，也许通过使用超过10秒的速率的均值，超过1分钟的速率超过1小时？ 某种人为的过滤方式，如“如果我的新估计与以前的估计有很大的差别，请调低它，不要让它反弹太多”？ 一些奇特的历史分析，你整合的进度与时间的进步，find标准差的速度给完成统计误差度量？
你有什么尝试，什么效果最好？
原始答复
创build这个网站的公司显然做出了一个调度系统，在员工编写代码的上下文中回答这个问题。 它的工作方式是基于过去的蒙特卡罗模拟未来。
附录：蒙特卡罗的解释
这就是这种algorithm如何在你的情况下工作：
你把你的任务build模成一系列微任务，比如1000个。 假设一小时后你完成了100个。 现在，通过随机select90个完成的微任务，将剩下的900个步骤进行模拟，并将其乘以10。 重复N次，剩余时间有N次估计。 请注意，这些估计之间的平均时间将是大约9个小时 – 这里并不意外。 但是通过向用户呈现分配结果，你会诚实地向他传达赔率，例如“有90％的可能性，这将需要3-15小时”
按照定义，这个algorithm如果可以将所讨论的任务build模为一堆独立的随机微任务，则会产生完整的结果。 只有当你知道任务偏离这个模型时，你才能得到更好的答案：例如，安装者通常有一个下载/解包/安装任务列表，而一个人的速度不能预测另一个。
附录：简化蒙特卡罗
我不是一个统计学专家，但是我认为，如果在这个方法中仔细观察模拟，它总是会返回一个正态分布作为大量独立随机variables的总和。 因此，你根本不需要执行它。 事实上，你甚至不需要存储所有完成的时间，因为你只需要他们的总和和他们的平方和。
在也许不是很标准的表示法中，
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％，但是我可能错过了一些常数因子）。
这是我发现的作品！ 对于任务的第一个50％，你认为这个比率是恒定的和外推的。 时间预测非常稳定，不会反弹太多。
一旦你通过50％，你切换计算策略。 你把剩下的工作的一部分做（1-p），然后回顾一下你自己进度的历史，并find（通过二分search和线性插值）多长时间你做最后一个（1 -p）百分比，并使用它作为您的时间估计完成。
所以如果你现在完成了71％，你还剩下29％。 你回顾你的历史，发现你在（71-29 = 42％）完成之前多久。 报告时间作为您的ETA。
这自然是适应性的。 如果你有X个工作要做，那么只需要花费X个工作量。 最后，当你完成了99％的时候，它只使用非常新的，非常近的数据来估计。
这当然不是完美的，但它会顺利地变化，并且在最有用的时候是非常准确的。
我通常使用指数移动平均值来计算平滑系数为0.1的操作的速度，并使用它来计算剩余时间。 这样所有的测量速度对当前的速度都有影响，但是最近的测量结果比以前的测量结果要好得多。
在代码中，它看起来像这样：
alpha = 0.1 # smoothing factor ... speed = (speed * (1 - alpha)) + (currentSpeed * alpha)
如果你的任务大小一致， currentSpeed就是执行最后一个任务所花费的时间。 如果这些任务有不同的大小，并且您知道一个任务应该是另一个任务的两倍，那么可以将执行任务所花费的时间除以其相对大小以获得当前速度。 使用speed您可以通过将剩余时间乘以剩余任务的总大小来计算剩余时间（或者如果任务是统一的，则仅通过它们的数量来计算）。
希望我的解释清楚，今天有点晚了。
虽然所有例子都是有效的，但对于“下载时间”的具体情况，我认为查看现有的开源项目来查看它们的工作是一个好主意。
从我所看到的，Mozilla Firefox是估计剩余时间的最佳select。
火狐浏览器
Firefox会跟踪最后一次剩余时间的估计值，通过使用这个剩余时间的当前估计值，它会对时间执行一个平滑函数。 请参阅此处的ETA代码。 这使用了一个先前计算在内的“速度”，是最近10次读数的平均值。
这有点复杂，所以要解释一下：
- 以平均速度为基础，以前一次的速度为90％，新的速度为10％。
- 用这个平滑的平均速度计算剩余的估计时间。
- 使用这个剩余的估计时间，以及剩下的上一个估计时间创build一个新的估计剩余时间（为了避免跳跃）
谷歌浏览器
Chrome似乎在各处跳跃，代码显示了这一点 。
我喜欢用Chrome做的一件事情是如何格式化剩余时间。 对于> 1小时，表示“还剩1小时”。<1小时表示“剩下59分钟”。<1分钟表示“剩下52秒”
你可以在这里看到它是如何格式化的
的DownThemAll！ 经理
它没有使用任何聪明的东西，这意味着ETA跳跃到处都是。
看到这里的代码
pySmartDL（一个python下载器）
计算最近30次ETA计算的平均ETA。 听起来像是一个合理的方式来做到这一点。
请参阅此处的代码/blob/916f2592db326241a2bf4d8f2e0719c58b71e385/pySmartDL/pySmartDL.py#L651）
传输
在大多数情况下（除了开始时，可能会有所预期）提供了一个相当不错的ETA。
在过去的5次阅读中使用平滑因子，与Firefox类似，但不太复杂。 基本上类似于Gooli的答案。
看到这里的代码
在某些情况下，当您需要定期执行相同的任务时，使用过去的完成时间平均值可能是一个好主意。
例如，我有一个通过COM接口加载iTunes库的应用程序。 一个给定的iTunes资料库的大小一般不会从项目数量上的启动到启动，因此在这个例子中可能跟踪最后三个加载时间和加载速率，计算您当前的ETA。
这将比瞬时测量更准确，并且可能更一致。
但是，这种方法取决于任务的大小与以前的任务相对相似，所以这对于解压缩方法或其他任何给定的字节stream是要处理的数据的其他东西都是行不通的。
只是我的$ 0.02
首先，它有助于产生一个移动均线。 这更加重视更近期的事件。
要做到这一点，保持一堆样本（循环缓冲区或列表），每一个进度和时间。 保留最近的N秒样本。 然后生成样本的加权平均值：
totalProgress += (curSample.progress - prevSample.progress) * scaleFactor totalTime += (curSample.time - prevSample.time) * scaleFactor
其中scaleFactor从0 … 1线性变为过去时间的反函数（因此更加重视更近期的样本）。 当然，你可以玩这个权重。
最后，你可以得到平均的变化率：
averageProgressRate = (totalProgress / totalTime);
你可以用这个来计算ETA，把剩下的进度除以这个数字。
然而，虽然这给你一个很好的趋势数，但你有另一个问题 – 抖动。 如果由于自然的变化，你的进度会有一些变化（比如嘈杂） – 例如，也许你正在使用它来估计文件下载量 – 你会注意到噪音很容易导致你的ETA跳跃，特别是如果在未来几分钟甚至更远
为了避免抖动过多影响您的ETA，您希望这个平均变化率数字对更新缓慢地响应。 解决这个问题的方法之一是保持averageProgressRate的caching值，而不是立即将其更新为刚刚计算的趋势数字，而是将其模拟为具有质量的重物体，并将模拟的“力”将其移向趋势号码。 有了质量，它有一点惯性，不太可能受到抖动的影响。
这里有一个粗略的例子：
// desiredAverageProgressRate is computed from the weighted average above // m_averageProgressRate is a member variable also in progress units/sec // lastTimeElapsed = the time delta in seconds (since last simulation) // m_averageSpeed is a member variable in units/sec, used to hold the // the velocity of m_averageProgressRate const float frictionCoeff = 0.75f; const float mass = 4.0f; const float maxSpeedCoeff = 0.25f; // lose 25% of our speed per sec, simulating friction m_averageSeekSpeed *= pow(frictionCoeff, lastTimeElapsed); float delta = desiredAvgProgressRate - m_averageProgressRate; // update the velocity float oldSpeed = m_averageSeekSpeed; float accel = delta / mass; m_averageSeekSpeed += accel * lastTimeElapsed; // v += at // clamp the top speed to 25% of our current value float sign = (m_averageSeekSpeed > 0.0f ? 1.0f : -1.0f); float maxVal = m_averageProgressRate * maxSpeedCoeff; if (fabs(m_averageSeekSpeed) > maxVal) { m_averageSeekSpeed = sign * maxVal; } // make sure they have the same sign if ((m_averageSeekSpeed > 0.0f) == (delta > 0.0f)) { float adjust = (oldSpeed + m_averageSeekSpeed) * 0.5f * lastTimeElapsed; // don't overshoot. if (fabs(adjust) > fabs(delta)) { adjust = delta; // apply damping m_averageSeekSpeed *= 0.25f; } m_averageProgressRate += adjust; }
你的问题是一个很好的问题。 如果问题可以分解成不连续的单位，则精确的计算通常效果最好。 不幸的是，即使您安装了50个组件，每个组件都可能是2％，但是其中一个组件可能非常庞大。 有一件事，我已经取得了中等成功，就是计算CPU和磁盘，并根据观测数据给出一个合理的估计。 知道某些检查点实际上是指向x，使您有机会纠正环境因素（networking，磁盘活动，CPU负载）。 然而，这个解决scheme由于依赖于观测数据而不是一般性的。 使用诸如rpm文件大小之类的辅助数据帮助我使我的进度条更加准确，但它们绝不是防弹的。
我总是希望这些东西能告诉我一个范围。 如果说“这个任务很可能会在8分钟到30分钟之间完成”，那么我有一个什么样的rest的想法。 如果它到处跳动，我都会忍不住要看，直到它平静下来，这是一个很大的浪费时间。
统一平均
最简单的方法是线性预测剩余时间：
t_rem := t_spent ( n - prog ) / prog
其中t_rem是预测的ETA， t_spent是自开始操作以来所经过的时间，将完成的微任务的数量从完整数量n 。 解释 – n可能是要处理的表中的行数或要复制的文件数。
这种方法没有参数，不用担心衰减指数的微调。 由于所有的样本对估计的贡献相同，所以权衡是不适应变化的进展速度的，而只能满足最近的样本应该具有更多的权重，这导致我们
指数平滑率
其中标准技术是通过平均先前的点测量来估计进展率：
rate := 1 / (n * dt); { rate equals normalized progress per unit time } if prog = 1 then { if first microtask just completed } rate_est := rate; { initialize the estimate } else begin weight := Exp( - dt / DECAY_T ); rate_est := rate_est * weight + rate * (1.0 - weight); t_rem := (1.0 - prog / n) / rate_est; end;
其中dt表示上次完成的微任务的持续时间，等于自上次进度更新以来经过的时间。 请注意， weight不是一个常数，必须根据观察到特定rate的时间长度进行调整，因为我们观察到特定速度的时间越长，先前测量的指数衰减就越高。 常数DECAY_T表示样本的权重减lesse倍的时间长度。 SPWorley自己也提出了对gooli的提案的一个类似的修改，尽pipe他把它用于错误的用语。 等距测量的指数平均值为：
Avg_e(n) = Avg_e(n-1) * weight + (1 - weight) * m_n
但是如果样本不是等距的，那么典型进度条中的时间就是这样呢？ 考虑到上面的alpha只是一个经验商，其真实价值是：
alpha = Exp( - lampda * dt ),
其中lampda是指数窗口的参数，而dt是自上次采样以来的变化量，不需要时间，而是任何线性和附加参数。 alpha对于等距测量是恒定的，但是随dt而变化。
请注意，此方法依赖于预定义的时间常数，并且不能及时扩展。 换句话说，如果完全相同的过程被一个常数因子均匀减速，这个基于速率的滤波器将成比例地更敏感的信号变化，因为在每一步的weight将减less。 但是，如果我们想要独立于时间尺度的平滑，我们应该考虑
指数平滑的慢度
这实质上是平滑的利率上下颠倒了一个恒定的weight的增加简化，因为prog增长等距增量：
slowness := n * dt; { slowness is the amount of time per unity progress } if prog = 1 then { if first microtask just completed } slowness_est := slowness; { initialize the estimate } else begin weight := Exp( - 1 / (n * DECAY_P ) ); slowness_est := slowness_est * weight + slowness * (1.0 - weight); t_rem := (1.0 - prog / n) * slowness_est; end;
无量DECAY_P数DECAY_P表示两个样本之间归一化的进展差异，其中权重的比例为1到e 。 换句话说，这个常量决定了平滑窗口在进程域的宽度，而不是在时域。 因此，该技术与时间尺度无关并具有恒定的空间分辨率。
进一步的研究：自适应指数平滑
现在您可以尝试自适应指数平滑的各种algorithm。 只记得把它用于缓慢而不是评价 。
我已经尝试并简化了您的“简单”/“错误”/“确定”公式，并且最适合我：
t / p - t
在Python中：
>>> done=0.3; duration=10; "time left: %i" % (duration / done - duration) 'time left: 23'
与（dur *（1-done）/ done）相比，这节省了一个操作。 而且，在你所描述的边缘情况下，可能无视对话30分钟，在等待了整晚之后更加不容易。
比较这个简单的方法， 使用传输 ，我发现它高达72％更准确。
我不汗，这是应用程序的一小部分。 我告诉他们发生了什么事，让他们去做别的事情。
