4

给定一个线函数 y = a*x + b（a和b是先前已知的常数），很容易计算线和样本窗口之间的平方和距离(1, Y1), (2, Y2), ..., (n, Yn)（其中Y1最旧的样本和Yn最新的样本）：

sum((Yx - (a*x + b))^2 for x in 1,...,n)

我需要一个快速算法来计算滚动窗口（长度n）的这个值 - 每次新样本到达时，我都无法重新扫描窗口中的所有样本。
显然，对于每个进入窗口的新样本和每个离开窗口的旧样本，都应该保存和更新一些状态。
请注意，当一个样本离开窗口时，其余样本的指数也会发生变化——每个 Yx 都变为 Y(x-1)。因此，当一个样本离开窗口时，窗口中的每个其他样本都会为新总和贡献一个不同的值：(Yx - (a*(x-1) + b))^2而不是(Yx - (a*x + b))^2.

有没有已知的算法来计算这个？如果没有，你能想到一个吗？（由于一阶线性近似，有一些错误是可以的）。

4

2 回答 2

2

一个简单的方法不会解决问题吗？...

“直截了当”是指维护样本队列。收到新样品后，您将：

  • 从队列中弹出最旧的样本
  • 从你的总和中减去它的距离
  • 将新样本附加到队列中
  • 计算它的距离并将其添加到您的总和中

至于时间，如果队列被实现为链表或类似的东西，这里的一切都是 O(1)，您也希望将样本的距离存储在队列中，因此您只计算一次。因此，每个样本的内存使用量为 3 个浮点数 - O(n)。

于 2012-01-06T00:11:40.447 回答
1

如果您扩展该术语(Yx - (a*x + b))^2，则该术语分为三个部分：

  1. 只有a和x的条款b。这些在相加时会产生一些常数n，可以忽略不计。
  2. 只有Yx和的条款b。这些可以像@Xion 描述的那样以棚车集成器的方式处理。
  3. 一个任期-2*Yx*a*x。-2*a是一个常数，所以忽略那部分。考虑部分总和S = Y1*1 + Y2*2 + Y3*3 ... Yn*n。给定Y1和一个运行总和R = Y1 + Y2 + ... + Yn，您可以找到S - R它消除Y1*1和减少每个其他项，留下Y2*1 + Y3*2 + ... + Yn*(n-1). R现在通过减去Y1和添加来更新 (2) 的运行总和Y(n+1)。将新Yn*n术语添加到S.

现在只需将所有这些部分项相加即可。

于 2012-01-06T00:40:41.950 回答