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

Question

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 1

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