Foldable-Queue(SWAG) およびそのDeque版について

初めに

今回はFoldableQueueというデータ構造、及びそれの拡張版であるFoldableDequeの実装について解説しようと思います。このデータ構造は競技プログラミング界隈においてSWAG(Sliding Window Aggregation)とも呼ばれています。もともと、SWAGという呼称は問題形式および操作に視点を当てた言い方で、個人的にはFoldableQueue(Deque)という呼び名の方を推していきたいと思っています。

今回の最終目標は、以下のクエリの処理が高速にできるデータ構造を作ることです。初期状態には、空の列があるとします。

1. 列の最後尾に値を追加する。
2. 列の先頭に値を追加する。
3. 列の最後尾から1つ値を取り出す。
4. 列の先頭から1つ値を取り出す。
5. 列全体の総積 ¹ を計算する。

事前準備: Deque,Stack,Queueについて

上に書いたクエリのうち、5を除いたもの

1. 列の最後尾に値を追加する。
2. 列の先頭に値を追加する。
3. 列の最後尾から1つ値を取り出す。
4. 列の先頭から1つ値を取り出す。

は、Dequeが $O(1)$ でできる操作そのものです。今回はDequeの（標準的な）実装²については触れませんが、多くの言語においてDequeはライブラリとして実装されており、簡単に使うことができます。
ただ、操作5をやるとなった場合、Dequeをそのまま使うことはできません。5で全部の要素を見て積を求めるなどとした場合、各操作ごとの計算量がデータサイズを $N$ として $O(N)$ となります。今回のデータ構造では、これも $O(1)$ でやりたいです。

足し算や掛け算なら、Dequeのままでもできます。今、「Deque内に入っているもの全部の積」を変数で持っておいて、出し入れする際に足したり引いたりすればいいです。しかし、これだとmaxやminのとき困ります。別の方法を考えましょう。

Dequeの下位互換的なデータ構造として、StackとQueueがあります。Stackは上の1,3のみ、Queueは上の1,4のみ $O(1)$ でできるデータ構造です。これらを使って、目標を達成するデータ構造を作っていきます。

Two-Stack Queueについて

さて、先ほど出てきたStackとQueueについて整理します。
Stack:

1. 列の最後尾に値を追加する。
2. 列の最後尾から1つ値を取り出す。

Queue:

1. 列の最後尾に値を追加する。
2. 列の先頭から1つ値を取り出す。

取り出す方向に違いがあります。実は、Stackを2つ使うことでQueueと同じ働きをするデータ構造が作れます。これについて説明します。

Two-Stacks Queueの実装

まず、「前側」と「後側」の2つのStackを用意します。そして、各クエリについて以下のようにします。

1. 列の最後尾に値を追加する。
   このクエリでは、後側のStackにそのまま値を挿入します。
2. 列の先頭から1つ値を取り出す。
   このクエリが問題となります。そのままでは後側にしかデータが溜まらず、先頭の値を取り出すことができません。それに対処するために、このクエリが来た時前側に値がないなら、後側の値をひっくり返して全部前側に突っ込むことにします。こうすると、前側のStackの最後尾が元の先頭の値となって、無事（元の）先頭の値を取り出すことができます。

図説

前側  後側
    | 12345 初めの状態。後側にしか値がないので、取り出せない
    ↓

前側  後側
    | 　　　(12345 いったん、全部取り出す
    ↓

前側   後側
12345  | 　　　 前側のStackにすべての値を入れる。よって、前から値を取り出せるようになる。

Two-Stacks Queueの時間計算量解析

ある1つの値に注目します。ある値がTwo-Stacks Queueに入ってから出るまでに、以下のような過程を経ます。

後側に入る→後側から前側に移動する→前側から出る

クエリによって移動回数は減ることもあります（例えば、最後まで取り出されず終わる場合などがあります）が、最大でも3回しか移動操作を行わないことが分かります。よって、計算量はならし $O(1)$ ³ となります。

Foldable-Stack について

下準備2です。以下のことが全部 $O(1)$ でできるデータ構造を作ります。

1. 列の最後尾に値を追加する。
2. 列の最後尾から1つ値を取り出す。
3. 列全体の総積 ¹ を計算する。

Stackに総積を計算する機能を付けたものです。これは、元の値を入れるStackと、その累積を入れるStackの2つを持つことで実現できます。追加/削除で、元の値とStackを両方追加したり削除したりすればいいです。
総積については、累積Stackの最後尾の値が答えです。

総積をminとした場合の具体例を示します。

Foldable Stack: 最小値の場合

元の値 | 2 3
累積　 | 2 2 現在の全体の最小値は、累積Stackの最後尾2である
↓ 値1を追加
元の値 | 2 3 1
累積　 | 2 2 1 現在の全体の最小値は、累積Stackの最後尾1である
↓ 最後尾を削除
元の値 | 2 3
累積　 | 2 2 現在の全体の最小値は、累積Stackの最後尾2である
↓ 最後尾を削除
元の値 | 2
累積　 | 2 現在の全体の最小値は、累積Stackの最後尾2である

Foldable-Queue

ウイニングランです。先ほどのTwo-Stacks Queue でStackを使っていたところをFoldable-Stackに変えれば、Foldable-Queueの完成です。
注意点は2つあります。1つ目は、前側と後側のFoldable-Stackを持つことになるので、最終的な総積は前側の累積と後側の累積同士の積となります。
2つ目は、どちらかのStackが空になった場合の処理です。これの対処法は、単位元を作っておくことや、空の場合の例外処理を書くことなどがあります。
Pythonでの実装例を示します。（実装を簡潔にするため、単位元を要求しています）

class SWAG():
    def __init__(self, op, e):
        self.op = op
        self.e = e
        self.top = []
        self.bottom = []
        self.topfold = [e]
        self.bottomfold = [e]
    def _pushbottom(self, x):
        self.bottom.append(x)
        self.bottomfold.append(self.op(self.bottomfold[-1], x))
    def _popbottom(self):
        self.bottomfold.pop()
        return self.bottom.pop()
    def _pushtop(self, x):
        self.top.append(x)
        self.topfold.append(self.op(x, self.topfold[-1]))
    def _poptop(self):
        self.topfold.pop()
        return self.top.pop()
    def push(self, x):
        self._pushbottom(x)
    def fold(self):
        return self.op(self.topfold[-1], self.bottomfold[-1])
    def pop(self):
        if not self.top:
            while self.bottom:
                x = self._popbottom()
                self._pushtop(x)
        if not self.top:
            return self.e
        else:
            return self._poptop()
    def front(self):
        if not self.top:
            while self.bottom:
                x = self._popbottom()
                self._pushtop(x)
        return self.top[-1]

Q. なんで名前がSWAGなんですか？
A. 人は初めて見た名前を刷り込まれてしまうからです。

Two-Stack Dequeについて

実は、Dequeも2つのStackを使うことで実装できます。Queueでは値は前からしか取り出されませんが、Dequeでは後ろから出ることもあります。よって、値が取り出せなくなった時、全部移すのではなくて、前と後ろで半分こすることにします。こうするだけで、Two-Stack Dequeが実装できてしまいます。

Two-Stacks Dequeの実装

まず、「前側」と「後側」の2つのStackを用意します。そして、各クエリについて以下のようにします。

1. 列の前/後に値を追加する。
   このクエリでは、前/後のStackにそのまま値を挿入します。

2. 列の前/後から1つ値を取り出す
   値を取り出せるときはそのまま取り出して終わりです。
   前/後側のStackに値が無くて取り出せないとき、もう片方から値を全部取り出し、順番が変わらないように気を付けながら半分ずつに分けて、取り出します。

特有の注意点としては、前後それぞれに移す操作があるため、移動させる際には、順番が変わらないよう気を付ける必要があることが挙げられます。特に、行列の積や1次関数の合成など非可換な演算を扱う場合は十分注意してください。

図説

前側  後側
    | 12345 初めの状態。後側にしか値がないので、取り出せない
    ↓

前側  後側
    | 　　　(12345 いったん、全部取り出す
    ↓

前側   後側
123  | 45　　　 半分ずつに分ける。こうすることで、前からも後ろからも取り出せる。

Two-Stacks Dequeの時間計算量解析

Queueのときと同様に、ある1つの値に注目します。ある値がTwo-Stacks Dequeに入ってから出るまでに、以下のような過程を経ます。

どっちかから入る→後側から前側に移動する→後側から前側に移動する→...→どっちかから出る

場合によってはめちゃくちゃ移動することになってやばいやんけ！となりますが、実は大丈夫です。移動するたびに個数が半分ずつになるので、

\frac{1}{2^1} + \frac{2}{2^2} + \dots + \frac{x}{2^x} \dots = 2

より、後側から前側に移動する→後側から前側に移動する→...の部分は操作回数2回と見積もれて、合計で操作回数は4回になります。⁴ よって、計算量はならし $O(1)$ ³ となります。

Foldable-Queue

ウイニングラン2です。先ほどのTwo-Stacks Deque でStackを使っていたところをFoldable-Stackに変えれば、Foldable-Dequeの完成です。

Pythonでの実装例を示します。

class DSWAG():
    def __init__(self, op, e):
        self.op = op
        self.e = e
        self.top = []
        self.bottom = []
        self.topfold = [e]
        self.bottomfold = [e]
    def _pushbottom(self, x):
        self.bottom.append(x)
        self.bottomfold.append(self.op(self.bottomfold[-1], x))
    def _popbottom(self):
        self.bottomfold.pop()
        return self.bottom.pop()
    def _pushtop(self, x):
        self.top.append(x)
        self.topfold.append(self.op(x, self.topfold[-1]))
    def _poptop(self):
        self.topfold.pop()
        return self.top.pop()
    def push(self, x):
        self._pushbottom(x)
    def pushleft(self, x):
        self._pushtop(x)
    def fold(self):
        return self.op(self.topfold[-1], self.bottomfold[-1])
    def popleft(self):
        if not self.top:
            stack = []
            while self.bottom:
                x = self._popbottom()
                stack.append(x)
            n = len(stack)
            stack = stack[::-1]
            stack1 = stack[:(n+1)//2]
            stack2 = stack[(n+1)//2:][::-1]
            for _ in range((n + 1) // 2):
                self._pushtop(stack1.pop())
            for _ in range(n // 2):
                self._pushbottom(stack2.pop())
        if not self.top:
            return self.e
        else:
            return self._poptop()
    def pop(self):
        if not self.bottom:
            stack = []
            while self.top:
                x = self._poptop()
                stack.append(x)
            n = len(stack)
            stack1 = stack[:n//2]
            stack2 = stack[n//2:][::-1]
            for _ in range((n+1) // 2):
                self._pushbottom(stack2.pop())
            for _ in range(n // 2):
                self._pushtop(stack1.pop())
        if not self.bottom:
            return self.e
        else:
            return self._popbottom()

Q. なんで名前がDSWAGなんですか？
A. Deque版のSWAGというニュアンスです。

終わりに

Two-Stacks Deque 及び Foldable-Queue については、素晴らしい記事が他にもたくさんあります（参考文献をご覧ください）が、それらを合わせて書いてある記事は少ない（あるいは、ほぼ同様としてまとめられている）ので、書いてみました。

特に計算量周りの議論など、間違っている部分があるかもしれません。もし訂正できる方がいましたら、コメント欄やTwitter @Shirosvmkcp に連絡していただけると助かります。

参考文献

Foldable-Queueの実装についての有名記事です。とても参考になりました。

この記事の上位互換です。

potentialとaccounting methodを用いたTwo-Stacks Deque の計算量解析が載っています。

1. ここでいう「積」は、掛け算のことだけを指すのではなく、足し算、max/min、bit演算などいろいろなものを指しています（結合法則が成り立っていれば大丈夫です）。以降では、その演算1つ当たりの時間計算量が $O(1)$ であることを仮定します。 ↩ ↩²

2. 例えば双方向連結リストなどを使った実装が一般的であると思います。 ↩

3. 実際には、後から前に移動させる操作のときにいっぺんに全部移動させるので、その時だけ時間が多くかかります。しかし、ここで述べたように各要素ごとの計算量は定数になるので、操作1つあたりは $O(1)$と考えます。このような考え方を償却計算量またはならし計算量と呼びます。実際の速度も十分高速です。 ↩ ↩²

4. この辺の議論はかなり大雑把でヤバいと思います。（助けてください）ちゃんとした説明は参考文献をご覧ください。 ↩