用于估计具有异构迭代的时间密集型循环的剩余时间的算法

Question

我有一个指令循环，例如(伪代码):

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

这需要很长时间才能完成。我想向用户输出某种进度，更重要的是剩余时间估计，这样他们就可以决定是坐在那里玩弄自己的拇指，去喝杯咖啡，出去散散步，还是去度一个星期的假期到欧洲，同时算法处理其数字。

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

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

另一种方法是将自第一次迭代以来耗时除以完成的迭代次数，然后将其乘以剩余迭代次数。如果迭代持续时间分布不均，则此问题将失效。例如，如果前几个输入是“困难的”并且在输入数组的末尾变得更容易，算法将高估剩余时间直到它几乎完成(此时它会略微高估)。

因此，当每次迭代所花费的时间是一个非直接的任意函数时，如何才能更好地估计剩余时间(这样简单地分析推导和实现每次迭代的完成时间是不切实际的)迭代纵坐标？

我能想到的两个想法可能是富有成果的研究途径，但目前无法完全探索自己:

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

为什么计算密集型解决方案(如拟合方程)没问题:

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

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

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

Answer 1

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

for i = 1 to N
  f(i)

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

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