与えられたライン関数からローリングウインドウの二乗和の距離を計算するアルゴリズム

Question

与えられたライン関数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) 

Iは、（長さnの）ローリング・ウィンドウのために、この値を計算するための高速アルゴリズムを必要とする - 私はできません新しいサンプルが到着するたびにウィンドウ内のすべてのサンプルを再スキャンします。
明らかに、ウィンドウに入る新しいサンプルごとにいくつかの状態を保存して更新し、すべての古いサンプルがウィンドウを離れるようにする必要があります。
サンプルがウィンドウを離れると、残りのサンプルのindeciesも同様に変化し、すべてのYxはY（x-1）になります。したがって、サンプルがウィンドウを離れるとき、ウィンドウ内の他のすべてのサンプルは、(Yx - (a*x + b))^2の代わりに(Yx - (a*(x-1) + b))^2の新しい合計に異なる値を提供します。

これを計算するアルゴリズムはありますか？そうでなければ、あなたは1つ考えることができますか？ （一次線形近似のためにいくつかの間違いがあることは大丈夫です）。

Answer 1

あなたが用語を展開すると(Yx - (a*x + b))^2用語は、3つの部分に侵入：のみa、xとbの

1. 規約。これらは、nを合計したときに一定値を生成し、無視することができます。
2. の用語Yxおよびbのみ。これらは、@ Xionが記述されたboxcarインテグレータのスタイルで扱うことができます。
3. -2*Yx*a*xの1項。 -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)のままになります。 Y1を差し引いてY(n+1)を差し引くことにより、（2）と同様に実行合計Rを更新します。新しいYn*n用語をSに追加します。

これらの部分的な用語をすべて追加してください。

Answer 2

は簡単なアプローチは、トリックをしないのでしょうか？...

私はサンプルのキューを維持することを意味「簡単な」とは。新しいサンプルが到着すると、あなたが希望：

• は、その距離を計算し、それを追加
• キューに新しいサンプルを追加し、あなたの合計から
• をその距離を減算キュー
• から最も古いサンプルをポップあなたの合計に

キューはリンクされたリストまたは同様のものとして実装されている場合、ここでのすべてはO（1）です。キュー内のサンプルとの距離も保存したいので、計算しますそれだけyを一度。したがって、メモリ使用量は1サンプルあたり3フロート - O（n）です。