5

我有一个指令循环，例如（伪代码）：

for i = 1 to 1000000
    // Process the ith input
    doSomething(input[i])
end

这需要很长时间才能完成。我想向用户输出一些进度，更重要的是剩余时间估计，以便他们可以决定是否应该坐在那里玩弄拇指，去喝杯咖啡，去散步，或者去一个一周的假期到欧洲，而算法处理它的数字。

为了简化问题，您可以假设迭代次数会很大（例如，大于 100，因此您可以在每个百分位打印进度）。

一种常见的算法是简单地测量最后一次迭代所用的时间，然后将其乘以剩余的迭代次数并将其作为输出。如果每次迭代在执行所需的时间上可能有很大差异，这就会崩溃。

另一种方法是将自第一次迭代以来经过的时间除以完成的迭代次数，然后将其乘以剩余的迭代次数。如果迭代的持续时间不是均匀分布的，这就会崩溃。例如，如果前几个输入是“困难的”并且在接近输入数组的末尾变得更容易，则算法将高估剩余时间，直到它几乎完成（此时它会略微高估）。

那么，当每次迭代所花费的时间是迭代纵坐标的非直接的、任意的函数（这样简单地分析推导和实现每次迭代的完成时间是不切实际的）时，如何才能更好地估计剩余时间?

我可以想象的两个想法可能是富有成效的研究途径，但目前无法充分探索自己：

  • 完成每个过去迭代的时间乘以剩余迭代的指数平均值。
  • 用于完成每次迭代的跟踪时间，然后拟合函数并进行外推。

为什么计算密集型解决方案（如拟合方程）可以：

首先，对于值得讨论的真正大型任务，运行时间可能以小时或天为单位来衡量。现在复杂的数学运算需要几毫秒，所以增加的负担不会很大——在我上面的例子中，显然doSomething需要很长时间才能使做一些数学的成本相形见绌，否则我不会太在意精确估计剩余时间第一名。

其次，例如，可以将迭代分箱成百分位数。然后，估计器不会对“完成的迭代与所用时间”的数据集进行操作，而是对最多具有 100 个数据点的“完成百分比与所用时间”的数据集进行操作。这提供了进一步的复杂性：假设您的任务需要一天或更长时间才能完成。仅估计剩余时间的每一个百分比是完整的，这意味着对估计函数进行 100 次评估。当你已经花了一天的时间，额外的一分半钟来估计剩余时间没什么大不了的，但这已经给了你一个 1 秒的窗口来拟合方程，还有什么不是 - 1 秒是做数学的很多时间在现代系统上。因此，我欢迎计算密集型解决方案。

tl;dr：如何为非常冗长的任务过度设计一个准确的剩余时间估计函数。

4

3 回答 3

2

如果您想获得始终如一的良好预测，那么第二种方法（拟合和外推）可能会做得最好 - 但前提是拟合函数与作为索引函数的处理时间的真实依赖性合理匹配。例如，如果 f(n) 是 O(n^2) 算法，则预测

for i = 1 to N
  f(i)

大约需要 k*N^3 时间来解决。因此，将三次拟合到总时间应该提供一个很好的近似值，但拟合二次或指数可能比简单的完成百分比近似更差。同样，如果 f 为 O(2^n)，则任何多项式拟合都会大大低估剩余时间。这一切都假设 N 足够大，以至于真正的 O(n^2) 行为占主导地位。

因此，虽然精心选择的拟合函数应该能够准确预测剩余时间，但通用预测函数不太可能有用。

于 2012-08-20T04:20:11.933 回答
1

除了 Penguino 的算法：您可能想要拟合 log(n) 和 log(f(n))，而不是拟合 n 和 f(n)。只要您的复杂性是多项式的，这将起作用。

于 2012-08-20T05:33:37.180 回答
0

我以前做过这样的事情。我发现创建一个非常准确的时间估计的最简单方法是（再次，在 p 代码中）：

initTime = getTime()
for i = 0 to maxIter
    doSomething()
    remainTime = convertToHoursMinutes(((getTime - initTime)/i)*maxIter)
next

这样，每次迭代你的“平均”时间就会减少，并且在 30-50 次迭代之后，你的用户可能对剩余时间有一个很好的了解（最终，中心极限定理开始发挥作用）。

于 2012-08-20T01:07:53.060 回答