SWAG(Sliding Window Aggregation)再考

本記事は1年半ほど前に執筆した
motsu-xe.hatenablog.com
という記事の続編ではあるのですが、暇な人以外はそっちは読まないでもいいです。

(忙しい人はしばらく下まで読み飛ばしてください)
こんにちは、Motsu_xeです。ありがたいことに、前作の記事はGoogle検索の影響もあり、未だにちょくちょくアクセスされているのですが、話題になってたから調べてみて、よくわかんなかったのがわかった！と思ったタイミングで、自分の浅い理解に基づいて書かれた記事となっておりますので、流石にこれを皆様にそのままご提供し続けるのもどうかと思い*1、筆をとった次第です。

本記事は、前回の浅い理解から、相対的に深くなった理解で、SWAGを今の私の理解に基づいて、解説していきたいと考えています。正直前の記事は消したい気持ちすらありますが、ありがたいことにあれを読んでSWAG理解できた、みたいな声を何人か聞いておりますので、まああれも人によっては刺さるかなということで残してはおきます。

前提知識

stack
queue
半群の定義*2
償却計算量の概念*3

SWAGとは

前回の記事では、SWAGを半群の列に対して、連続する要素の総積を尺取り的に求めるデータ構造として紹介しましたが、今回は少し変えます。

Sliding Window Aggregationとは、以下の4つの操作を、時間計算量償却 $\Theta(1)$ で実行するデータ構造である。

$\mathrm{new}()$ 半群の元を要素とする空のqueueを生成する

$\mathrm{push}(x)$ queueに $x$ を追加する

$\mathrm{pop}()$ queueの先頭の要素を削除する

$\mathrm{fold}()$ queueに入っている要素の総積*4を計算する

$\mathrm{new}()$	半群の元を要素とする空のqueueを生成する
$\mathrm{push}(x)$	queueに $x$ を追加する
$\mathrm{pop}()$	queueの先頭の要素を削除する
$\mathrm{fold}()$	queueに入っている要素の総積*4を計算する

少し考えると、前回のデータ構造と本質的に同じであることがわかると思います。

SWAGのstack版

SWAGは少し難しいので、少し変更してstackで同じことを考えます。STAGとでも呼びましょうか。つまり

STAGとは、以下の4つの操作を、時間計算量償却 $\Theta(1)$ *5で実行するデータ構造である。

$\mathrm{new}()$ 半群の元を要素とする空のstackを生成する

$\mathrm{push}(x)$ stackに $x$ を追加する

$\mathrm{pop}()$ stackの末尾の要素を削除する

$\mathrm{fold}()$ stackに入っている要素の総積を計算する

$\mathrm{new}()$	半群の元を要素とする空のstackを生成する
$\mathrm{push}(x)$	stackに $x$ を追加する
$\mathrm{pop}()$	stackの末尾の要素を削除する
$\mathrm{fold}()$	stackに入っている要素の総積を計算する

を考えます。これは簡単で、stack内の要素の累積積を保持しておけば、簡単に実行できます。擬似コードで書くと以下のようになりす。

new():
    st = stack()

push(x):
    if st.empty():
        st.push(x)
    else:
        st.push(top(st) * x)

pop():
    pop(st)

fold():
    return st.top()

two-stack queue

一旦SWAGのことは忘れて、queueについて考えます。queueはstack2本で再現することができます。詳しい話は他の記事に譲ることにして、擬似コードで書くと

new():
    stf = stack()
    stb = stack()

push(x):
    stb.push(x)

move():
    if stf.empty():
        while not stb.empty():
            stf.push(stb.top())
            stb.pop()

pop():
    move()
    stf.pop()

front():
    move()
    return stf.top()

のようになります。stfからstbに要素を移すタイミングで要素数だけ時間がかかりますが、各要素は、pushされてからpopされるまでに、高々1回しか移動しないことを考えれば、償却 $O(1)$ となっていることがわかります。

stack上のデータ構造をqueueに載せる

上で述べたstack版のSWAGを2つ用意すると、two-stack queueを用いることで、SWAGを実装することができます。これは、queue全体に対するfoldが、2つのstackのそれぞれのfoldの結合により求められることからわかります。ただし、非可換の場合は若干注意が必要で、2つのstackに乗っている半群は、演算を左右反転させたものとなっていて、stbには半群 $S$ 、stfには $S^{\mathrm{op}}$ が載っているという感じになっています。*6また、moveするときに、back側の累積を取る前の生データが必要になることに注意すると、次の擬似コードのように実装できます。

new():
    stf = STAG<S^op>()
    stb = STAG<S>()
    stb_row = stack()

push(x):
    stb.push(x)
    stb_row.push(x)

move():
    if stf.empty():
        while not stb.empty():
            stb.pop()
            stf.push(stb_row.top())
            stb_row.pop()

pop():
    move()
    stf.pop()

fold():
    if stf.empty():
        return stb.fold()
    if stb.empty():
        return stf.fold()
    return stf.fold() * stb.fold() //stf.fold()の値もSの元と解釈する

これでSWAGの本質は説明終了です。実際に実装するときは、わざわざSTAGのようなものは作らず、そのまま書いた方がわかりやすいです。*7

応用

queueと同様、dequeも2つのstackにより再現できることが知られています。詳しくは他の記事に譲りますが、two-stack queueとほぼ同様で、popしようとしたときに、popしたいstackが空だったら、半々に分けるみたいな感じでできます。STAGをSWAGにした時のことを思い出すと、ほとんど同様に、dequeにfoldを搭載することが可能になります。*8

まとめ

それなりに自分の頭の中では整理されていたので、いい記事になるだろうなぁと思いながら書いたのに、結局微妙になってしまい、思考のアウトプットが苦手で困るなぁという気持ちになっています。ご指摘あればお待ちしてます。ご精読ありがとうございました。

*1:そもそもブログの入りの挨拶から痛すぎてみてられない

*2:結合則を満たす演算を備えた集合のこと。よくわからなければ、整数での掛け算とかminとかgcdとか思っていただければ。

*3:知らないでもまあいい

*4:可換半群とは限らないので先頭要素から順番に積を考える

*5:多分stackは普通償却計算量じゃないかな…？最低でもstd::stackは実態がstd::dequeだったはずなので、償却のはず

*6:よくわからない人は可換の場合だけ考えるなら、とりあえず無視してok

*7:無駄をさらに削ぎ落としたものが、前回の記事のものなんですが、SWAGの概念をまず知るためには分かりづらい気がするんですよね。

*8:多分!!実装はしてません。もし実装するなら、生データはランダムアクセス可能なdequeとかを使って保持しておくと実装が楽かなぁという気がしてます。

Motsu_xe 競プロのhogeやfuga

Motsu_xeが競技プログラミングに関する何かを適当に書き連ねるブログになるはずです。

前提知識

SWAGとは

SWAGのstack版

two-stack queue

stack上のデータ構造をqueueに載せる

応用

まとめ