智能进度条预计到达时间

小开

我不担心，这只是申请中很小的一部分。我告诉他们发生了什么，然后让他们去做别的事。

小开

你的问题很好。如果问题可以分解成离散的单位，有一个准确的计算往往是最好的工作。不幸的是，即使您安装了50个组件，每个组件可能只占2% ，但其中一个组件可能非常庞大，情况可能并非如此。有一件事我已经取得了中等的成功，那就是计算 CPU 和磁盘的时钟，并根据观测数据给出一个不错的估计。知道某些检查点实际上是 x 点可以让您有机会修正环境因素(网络、磁盘活动、 CPU 负载)。然而，由于这种解决办法依赖于观测数据，因此在性质上不是一般性的。使用辅助数据，如 rpm 文件大小帮助我使我的进度条更准确，但他们从来没有防弹。

小开

在某些情况下，当您需要定期执行相同的任务时，使用过去的完成时间作为平均值可能是一个好主意。

例如，我有一个应用程序，它通过 COM 接口加载 iTunes 库。一个给定的 iTunes 库的大小通常不会从启动到启动的数量急剧增加，所以在这个例子中，可以跟踪最后三次加载时间和加载速率，然后根据这个平均值计算你当前的预计时间。

这将比瞬时测量精确得多，而且可能也更加一致。

但是，这个方法依赖于任务的大小与前面的任务相对相似，因此这对于解压缩方法或者其他任何给定字节流是要处理的数据的方法都不起作用。

只有我的0.02美元

小开

最佳答案

原始答案

创建这个网站的公司显然一个调度系统，回答这个问题的上下文中的员工编写代码。它的工作方式是基于过去的蒙特卡罗模拟未来。

附录: 蒙特卡罗解释

这就是这个算法在你的情况下的工作原理:

您将您的任务建模为一系列微任务，比如说1000个微任务。假设一个小时后你完成了其中的100个。现在，通过随机选择90个已完成的微任务，将它们的时间相加并乘以10，运行剩余900个步骤的模拟。这里有一个估计，重复 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% 左右，但是我可能错过了某个常数因子)。

小开

我一直希望这些东西能告诉我一个范围。如果它说，“这个任务最有可能在8分钟到30分钟之间完成”，那么我就有了一些休息的想法。如果它到处反弹，我会忍不住看着它，直到它平静下来，这是一个很大的时间浪费。

小开

我通常使用指数移动平均线来计算平滑因子为0.1的运算速度，并用它来计算剩余时间。这样一来，所有测量的速度都会对当前的速度产生影响，但最近的测量结果要比遥远的过去产生更大的影响。

在代码中，它看起来像这样:

alpha = 0.1 # smoothing factor
...
speed = (speed * (1 - alpha)) + (currentSpeed * alpha)

如果您的任务在大小上是一致的，那么 currentSpeed就是执行最后一个任务所花费的时间。如果任务有不同的大小，并且你知道一个任务应该是 i，e，两倍于另一个任务的长度，你可以用任务的相对大小除以执行任务所花费的时间来得到当前的速度。使用 speed，您可以通过将其乘以剩余任务的总大小来计算剩余时间(或者如果任务是统一的，仅仅乘以它们的数目)。

希望我的解释足够清楚，现在有点晚了。

小开

我发现这个方法很有效！对于任务的前50% ，假设速率为常数并进行推断。时间预测非常稳定，不会反弹太多。

一旦你通过50% ，你的开关计算策略。你取剩下的工作的一部分(1-p) ，然后回顾你自己的进展历史，找到(通过二进制搜索和线性插值)你花了多长时间完成最后一个(1-p)的百分比，并使用那个作为你估计完成的时间。

所以如果你现在完成了71% ，你还剩下29% 。你回顾你的历史，发现多久以前你是在(71-29 = 42%)完成。报告预计到达时间。

这是自然适应。如果你有 X 个数量的工作要做，它只看它所花费的时间来做 X 个数量的工作。最后，当你完成了99% ，它只是使用非常新的，非常近期的数据进行评估。

它当然不是完美的，但是它可以平稳地改变，尤其是在最有用的时候，它的最后部分是非常精确的。

小开

首先，它有助于产生一个连续的移动平均线，这将更加重视最近发生的事件。

要做到这一点，保持一堆样品周围(循环缓冲区或列表) ，每一对的进度和时间。保存最近 N 秒的样品。然后生成样本的加权平均数:

totalProgress += (curSample.progress - prevSample.progress) * scaleFactor
totalTime += (curSample.time - prevSample.time) * scaleFactor

scaleFactor 从0... 1到过去的时间反函数是线性的(因此对近期样本的权重更大)。当然，你可以调整这个权重。

最后，你可以得到平均变化率:

 averageProgressRate = (totalProgress / totalTime);

您可以使用这个函数，通过将剩余的进度除以这个数字来计算预计到达时间。

然而，虽然这给了你一个很好的趋势数字，你还有一个问题-抖动。如果，由于自然的变化，你的进度变动了一点(它的噪音)-例如，也许你正在使用这个来估计文件下载-你会注意到，噪音可以很容易地导致你的 ETA 跳转，特别是如果它是相当遥远的未来(几分钟或更多)。

为了避免抖动过多地影响您的预计到达时间，您希望这个平均变化率能够缓慢地响应更新。解决这个问题的一种方法是保持一个 averageProgressRate 的缓存值，而不是立即将它更新到你刚刚计算的趋势值，你把它模拟成一个有质量的重物体，施加一个模拟的“力”使它慢慢向趋势值移动。对于质量，它有一点惯性，不太可能受到抖动的影响。

下面是一个粗略的例子:

// 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;
}

小开

我尝试并简化了你的“简单”/“错误”/“ OK”公式，它对我最有效:

t / p - t

在 Python 中:

>>> done=0.3; duration=10; "time left: %i" % (duration / done - duration)
'time left: 23'

这比(dur * (1-done)/done)节省了一个操作。而且，在你描述的边缘情况下，可能忽略对话30分钟，在等待了一夜之后几乎没有关系。

将这个简单的方法与变速器用的那个进行比较，我发现它比变速器用的那个的精确度高出72% 。

小开

虽然所有的例子都是有效的，但对于“剩余下载时间”的特定情况，我认为最好看看现有的开源项目，看看它们能做些什么。

在我看来，MozillaFirefox 在估计剩余时间方面是最好的。

Mozilla Firefox

Firefox 会跟踪剩余时间的最后估计值，通过使用这个估计值和当前剩余时间的估计值，它在时间上执行了一个平滑功能。请参阅预计到达时间代码给你。这使用了一个“速度”，这是以前计算的给你，是一个平滑的平均值的最后10个读数。

这个问题有点复杂，可以这样解释:

采取平滑的平均速度的基础上，90% 的以前的速度和10% 的新的速度。
用这个平滑的平均速度计算出剩余的估计时间。
使用这个估计剩余时间，以及之前的估计剩余时间来创建一个新的估计剩余时间(以避免跳转)

谷歌浏览器

Chrome 浏览器似乎跳来跳去，代码显示了这个。

不过，我喜欢 Chrome 的一点是它们对剩余时间的格式化。对于 > 1小时，它说’1小时左’ 在不到1小时的时间里，上面写着“还剩59分钟” 在不到1分钟的时间里，上面写着“还剩52秒”

您可以看到它是如何格式化给你的

DownThemAll! 经理

它没有使用任何聪明的东西，也就是说预计到达时间到处乱窜。

参见这里的代码

PySmartDL (一个 Python 下载程序)

根据过去30年的平均预计到达时间计算，听起来是个合理的方法。

参见代码给你/blob/916f2592db326241a2bf4d8f2e0719c58b71e385/pySmartDL/pySmartDL.py # L651)

变速器

在大多数情况下给出了一个相当好的预计到达时间(除非在开始时，正如可能预期的那样)。

在过去的5次阅读中使用了一个平滑因子，类似于 Firefox，但没有那么复杂。与古利的答案基本相似。

看代码给你

小开

均匀平均

最简单的方法是线性预测剩余时间:

t_rem := t_spent ( n - prog ) / prog

其中 t_rem是预测的 ETA，t_spent是从操作开始以来经过的时间，prog是完成的微任务数量超出其全部量的 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表示样品重量减少一个 <你好m>你好因子的时间长度。SPWorley本人建议对 Gooli的提议进行类似的修改，尽管他用错了术语。等距离测量的指数平均值是:

Avg_e(n) = Avg_e(n-1) * alpha + m_n * (1 - alpha)

但是，如果样本不是等距离的，就像典型的进度条中的时间一样，那该怎么办呢？考虑到以上 alpha只是一个经验商数，其真实值是:

alpha = Exp( - lambda * dt ),

其中 lambda是指数窗口的参数，dt是自前一个样本以来的变化量，它不需要时间，而是任何线性和可加的参数。对于等距离测量，alpha是恒定的，但是随着 dt的变化而变化。

请注意，此方法依赖于预定义的时间常数，并且在时间上不可伸缩。换句话说，如果完全相同的过程被一个恒定的因子均匀地减慢，这种基于速率的滤波器将成比例地对信号变化更敏感，因为在每一个步骤 weight将减少。然而，如果我们想要一个独立于时间尺度的平滑，我们应该考虑

慢度的指数平滑

基本上就是把速率颠倒过来的平滑，再加上常数 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表示两个样本之间的标准化进度差，其中的权重是一对 <你好m>你好的比率。换句话说，这个常数决定了进度域中平滑窗口的宽度，而不是时间域中的宽度。因此，这种技术与时间尺度无关，具有恒定的空间分辨率。

进一步研究: 自适应指数平滑

您现在已经具备了尝试自适应指数平滑法的各种算法的能力。只要记住将它应用于缓慢而不是税率。