Two-Stack Sliding-Window Aggregation

Two-Stack Sliding-Window Aggregation 2026-10-02 集計とは、データのセットの何らかの要約です。これは合計、長さ、最小値などである可能性があります。このような要約を繰り返し計算したいことはよくあります。例えば、「過去30秒間のデシベル単位の最大ノイズレベル」を迷惑検出器のために計算したい場合などです。このような場合、データ上にスライディングウィンドウがあるといい、ウィンドウ上で集計を計算したいと言います。もし集計が逆元を持つ二項演算子（整数合計など）であれば、両端キュー（double-ended queue）を使った非常に簡単な解決策があります。 ```python from collections import deque class SlidingWindowSum: def __init__(self): self.sum = 0 self.elems = deque() def push(self, x): self.sum += x self.elems.append(x) def pop(self): self.sum -= self.elems.popleft() def eval(self): return self.sum ``` しかし、演算子に逆元がない場合はどうでしょうか？これは実際には、最小値、分位数、近似ユニークカウント（例えばHyperLogLogを使用するなど）のような、より興味深い要約のほとんどの場合に当てはまります。実際、浮動小数点数の合計のような単純なものでさえ、浮動小数点数の加算が可逆ではないという事実から影響を受けます。例えば、上記の単純なアルゴリズムで入力データにNaNが含まれている場合、悪い値がウィンドウから完全に削除された後でも、合計は永遠にNaNのままになります。 6年前に、スライディングウィンドウ内の最小値/最大値のみを維持するアルゴリズムを考案し、cs.stackexchangeに投稿しました。今ではこのアルゴリズムは無意味だと考えています。なぜなら、非常に幅広いクラスの集計問題を解決する、シンプルで効率的なアルゴリズムが存在することがわかったからです。このアルゴリズムはもっと広く知られるべきだと感じているので、このブログ記事を書いています。 伝承 このアルゴリズムに出会ったのは、はるかに高度な論文「Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time」by Tangwongsan et al. を読んでいるときでした。なぜこの論文は低レイテンシと題されているのでしょうか？それは、これから説明することと同じことを、各ステップでO(1)の時間で行うからです。しかし、その中で彼らは「2スタック」アルゴリズムも説明しており、それはアモルタイズO(1)で実行され、はるかに、はるかにシンプルです。面白いことに、その論文はこのアルゴリズムを2011年のStack Overflowの投稿の「adamax」に帰しています。彼らはさらに、2001年のD. Sleatorによる講義ノートにインスピレーションを求めています。しかし、この講義ノートはスライディングウィンドウ集計を説明しているのではなく、FIFOキューを実装するための古典的な2スタックアルゴリズムを説明し、それに対してアモルタイズ分析を行っています。最終的に、このアルゴリズムがどれほどシンプルで素晴らしいかを考えると、1970年代のどこかの難解な論文にすでに記述されていたとしても驚きません。 2スタック 論文の著者たちと同様に、私は2スタックアルゴリズムを任意の結合的な集計関数に一般化します。集計を、empty()、unit(x)、combine(x, y)、finalize(x) の一連の関数として抽象化することで、例えば平均のような多くの可能な集計を記述できます。 ```python empty = lambda: (0, 0) unit = lambda x: (x, 1) combine = lambda x, y: (x[0] + y[0], x[1] + y[1]) finalize = lambda x: x[0] / x[1] if x[1] else None ``` これらの関数は次のシグネチャを持つことに注意してください。 fn empty() -> Agg; fn unit(x: Value) -> Agg; fn combine(x: Agg, y: Agg) -> Agg; fn finalize(x: Agg) -> Out; Value、Agg、Outの間で区別を設けています。なぜなら、整数合計のようなものではそれらが表面的に似ていても、文字列上の近似ユニークカウントでは（Value, Agg, Out）=（String, HyperLogLogSketch, u64）となり、3つの全く異なる型になるからです。 早速ですが、アルゴリズムを紹介します。 ```python class TwoStackAgg: def __init__(self): self.values = [] self.values_agg = empty() self.cum_aggs = [] def push(self, x): self.values.append(x) self.values_agg = combine(self.values_agg, unit(x)) def pop(self): if not self.cum_aggs: cum_agg = empty() while self.values: cum_agg = combine(unit(self.values.pop()), cum_agg) self.cum_aggs.append(cum_agg) self.values_agg = empty() self.cum_aggs.pop() def eval(self): return finalize( combine(self.cum_aggs[-1], self.values_agg) if self.cum_aggs else self.values_agg ) ``` これだけです、アルゴリズム全体です。2つのスタック（valuesとcum_aggs）と、もう1つの集計値（values_agg）があります。任意の時点で、values_aggはvaluesの集計値を保持し、cum_aggsはvaluesに含まれていないウィンドウ内のすべての値の累積集計値を逆順に格納します。ここから、cum_aggsの最後の値とvalues_aggを結合することで、ウィンドウ全体の集計値を定数時間で取得できます。面白いのは、（wをウィンドウサイズとすると）w回の操作ごとにvaluesをすべて drain し、部分的な累積集計値をcum_aggsにプッシュしながら、実行中の集計値を維持することです。これがアモルタイズO(1)を実現している理由です。w回の操作ごとにO(w)の内部操作を行うことで、個々の操作は定数時間ではないかもしれませんが、要素あたりの総作業量をO(1)に制限します。 これを視覚化するのが最善だと思います。要素数4の固定サイズスライディングウィンドウで[1, 2, ..., 10]を合計すると仮定すると、各eval()呼び出し時の状態は次のようになります（values_aggはvaluesの集計値なので省略）。 cum_aggs | values | out ------- | -------- | --- [] | [] | 0 [] | [1] | 1 [] | [1, 2] | 1 + 2 [] | [1, 2, 3] | 1 + 2 + 3 [] | [1, 2, 3, 4] | 1 + 2 + 3 + 4 [4, 3 + 4, 2 + 3 + 4] | [5] | 2 + 3 + 4 + 5 [4, 3 + 4] | [5, 6] | 3 + 4 + 5 + 6 [4] | [5, 6, 7] | 4 + 5 + 6 + 7 [] | [5, 6, 7, 8] | 5 + 6 + 7 + 8 [8, 7 + 8, 6 + 7 + 8] | [9] | 6 + 7 + 8 + 9 [8, 7 + 8] | [9, 10] | 7 + 8 + 9 + 10 [8] | [9, 10] | 8 + 9 + 10 [] | [9, 10] | 9 + 10 [10] | [] | 10 [] | [] | 0 合計のメモリ使用量はO(w)です。ここでwは最大ウィンドウサイズです。分析と例の単純化のために固定サイズのウィンドウwを仮定しましたが、2スタックアルゴリズムがこれを必要とするという性質はありません。eval()の呼び出し間に好きなだけpush(x)とpop()を呼び出すことができ、ウィンドウサイズを必要に応じて増減させることができます。 浮動小数点数の非結合性 ここで、集計結合が結合的であること（つまり、combine(combine(x, y), z) = combine(x, combine(y, z))）を要求しました。厳密に言えば、浮動小数点数の加算はこの性質を尊重しません。それにもかかわらず、上記のアルゴリズムは、結果が期待される結果に非常に近いという点で、依然として非常に有用です。特に、Kahan summationのような補正付き加算アルゴリズムを使用すると、さらにそうです。しかし、上記のアルゴリズムには、もう1つ非常に有用な特性があります。各集計は厳密にウィンドウ内の要素の組み合わせであり、外部の要素は含まれません。これは、ウィンドウにNaNや無限大（またはその他の外れ値）が含まれている場合、その値は計算の他の部分を汚染するのではなく、それを含むウィンドウのみを汚染することを意味します。しかし、NaNや無限大がなくても有用です。なぜなら、エラーが無限に伝播しないからです。例えば、スライディングウィンドウが[1e20, 1]で始まると、単純なローリング合計では次のようになります。 >>> 1e20 + 1 - 1e20 - 1 -1.0 補正付き加算はこれらの効果を軽減しますが、結果がウィンドウ外の値に依存しないようにすることで、長期的な誤差の蓄積を完全に排除できます。