Pythonで各要素にO(1)でランダムアクセスできるdeque(両端キュー)を書いてみた

表題の通りなのですが、まず何が嬉しいかを説明します

Pythonで、from collections import deque とすると、 deque モジュールが使えます
これは、両端キューと呼ばれていて、両端の要素への追加や取り出しがいずれも $O(1)$ でできるリストのようなものです
これは単純な list と比較すると良さがわかって、
list は末尾への追加(append(x))、取り出し(pop()) が $O(1)$ でできる反面、先頭の追加(insert(0,x))、取り出し(pop(0)) は $O(N)$ かかってしまい、 $N$ が大きい時にたくさん呼び出すととても遅いです。¹

Pythonでは、Stack(LIFO)として配列を使いたい時は listで十分なのですが、 Queue(FIFO)として配列を使いたい時は dequeモジュールが必要になります。
もちろんdequeは両端キューなのでStack(LIFO)としても使えます。

しかし、dequeモジュールにも意外な弱点があります。
それはランダムアクセスの遅さです。
ここでランダムアクセスと言っているのは q[10] とか q[20] のようなindexを指定してのアクセスと思ってください。
deque モジュールでも、q[10] を参照したり、 q[20] = 'hoge' のように代入したりすることは可能ですが、遅いです
例えば、要素数 $N=200000$ の時に q[100000] を参照しようとするのは、内部的には端から順番に辿っていくので10万ステップぐらいかかります。
deque でのランダムアクセスは $O(N)$ かかると言えます。
一方、list ならindexからアドレスを直接算出できるので $O(1)$ です。

そこで、dequeモジュールの基本的な機能は抑えつつ、indexを指定しての参照・変更が $O(1)$ でできるモジュールを作ってみました

そんなことできるの？と思うかもしれませんが、螺旋本の91ページあたりにある「リングバッファ」を参考に書けそうだなと思ったので書いてみました
また、ざっと調べた感じC++のdequeは要素へのランダムアクセスは $O(1)$ のようですね
Javaの LinkedList も両端キューですが、こちらはランダムアクセスは $O(N)$ っぽいです
→有名な教訓 https://qiita.com/neko_machi/items/d620c4a8958e74df3550

実装

次のように実装しましたのよ

class Deque:
    def __init__(self, src_arr=[], max_size=300000):
        self.N = max(max_size, len(src_arr)) + 1
        self.buf = list(src_arr) + [None] * (self.N - len(src_arr))
        self.head = 0
        self.tail = len(src_arr)
    def __index(self, i):
        l = len(self)
        if not -l <= i < l: raise IndexError('index out of range: ' + str(i))
        if i < 0:
            i += l
        return (self.head + i) % self.N
    def __extend(self):
        ex = self.N - 1
        self.buf[self.tail+1 : self.tail+1] = [None] * ex
        self.N = len(self.buf)
        if self.head > 0:
            self.head += ex
    def is_full(self):
        return len(self) >= self.N - 1
    def is_empty(self):
        return len(self) == 0
    def append(self, x):
        if self.is_full(): self.__extend()
        self.buf[self.tail] = x
        self.tail += 1
        self.tail %= self.N
    def appendleft(self, x):
        if self.is_full(): self.__extend()
        self.buf[(self.head - 1) % self.N] = x
        self.head -= 1
        self.head %= self.N
    def pop(self):
        if self.is_empty(): raise IndexError('pop() when buffer is empty')
        ret = self.buf[(self.tail - 1) % self.N]
        self.tail -= 1
        self.tail %= self.N
        return ret
    def popleft(self):
        if self.is_empty(): raise IndexError('popleft() when buffer is empty')
        ret = self.buf[self.head]
        self.head += 1
        self.head %= self.N
        return ret
    def __len__(self):
        return (self.tail - self.head) % self.N
    def __getitem__(self, key):
        return self.buf[self.__index(key)]
    def __setitem__(self, key, value):
        self.buf[self.__index(key)] = value
    def __str__(self):
        return 'Deque({0})'.format(str(list(self)))

使い方

上のコードをコピペする。ドーン。

初期化

次のいずれかの形式で初期化します

q = Deque()
q = Deque([10, 20])
q = Deque([10, 20], 500000)

第1引数 src_arr はDequeとして初期化したい配列を指定してください。省略した場合は空です。
第2引数 max_size はDequeが内部で保持するバッファの長さを指定します。実行中に要素数が50万になる見込みなら、500000を指定してください。省略した場合は300000です。
- →必要に応じて拡張されるようにしたので基本気にしなくて良いです (2020/02/07 18時半頃update)
  - が、何度も初期化を呼び出す場合には10などの小さめの値を指定しておくことを推奨します (2024/01/09 update)

append, pop

この辺は collections.dequeモジュールと同じ感じで使えます

q = Deque([10, 20])
print(q) # Deque([10, 20])
q.append(30)
print(q) # Deque([10, 20, 30])
q.appendleft(40)
print(q) # Deque([40, 10, 20, 30])
a = q.pop()
print(q, a) # Deque([40, 10, 20]) 30
b = q.popleft()
print(q, b) # Deque([10, 20]) 40

indexを指定してのget, set

この辺も collections.dequeモジュールと使い勝手は一緒ですが、listのように $O(1)$ です！
Pythonらしく負のindexにも対応しています！

q = Deque([10, 20, 30, 40, 50])
a = q[1]
print(q, a) # Deque([10, 20, 30, 40, 50]) 20
q[1] = 60
print(q) # Deque([10, 60, 30, 40, 50])
b = q[-2]
print(q, b) # Deque([10, 60, 30, 40, 50]) 40
q[-2] = 70
print(q) # Deque([10, 60, 30, 70, 50])

型変換

list(q) のようにすれば list に変換できます！
set(q) で set に、list(reversed(q)) で逆順リストに変換できます
もちろん len(q) で要素数も取れます

できないこと・課題

~~メモリの動的確保~~
- ~~dequeモジュールは追加されたサイズに応じて拡張されるけれど、このDequeは初期化時の max_sizeを超えて格納はできません~~
  - ~~競プロ用途ならサイズが見積もれることが多いのであまり困らない気がする~~
- → max_size を超えて格納しようとするときに動的に領域を増やすように改修しました (2020/02/07 18時半頃update)
indexを指定しての挿入や削除とか、count() とか remove() とか
- 未実装 (実装するとしたらかな)
  - listに変換するのも $O(N)$ っぽいので困らなそう
rotate() とか
- 未実装 (実装するとしたらかな)
  - いる？
エラーハンドリングが甘いですけど
- よしなに使ってください

ところで

両端キューを使っているとき、ある要素に $O(1)$ でランダムアクセスしたくなる需要ってありますか？
たまにあった気がするけど思い出せない…
この問題に使えるかも！みたいなのがあったら教えてください！
あとツッコミや改善案などもあればTwitterで教えてください！

→使えると嬉しい問題が出ましたね！ (2021/06/09 8時頃update)

→使える問題が出ました！ (2024/01/09 update)

ABC335-C
- ごりちゃんライブラリにも掲載しました！

thanks

えびちゃんさんに改善案をもらったので改修しました (2020/02/07 18時半頃update)

リングバッファの大きさが一定値を超えたらその二倍の領域を確保する、というのを繰り返すことでならし定数時間にするやつ、などが有名そうです？
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2020年2月7日

先頭に要素を追加する場合は各要素をi番目→i+1番目にアドレスを動かさなきゃいけないからね。逆もしかり。↩

ごりちゃんがゆく

競プロをするゴリラの精進記録