30歳で競プロに目覚めた霊長類のブログ

チンパンジーと一般人のあいだ

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が大きい時にたくさん呼び出すととても遅いです。1

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)のようですね
JavaLinkedList も両端キューですが、こちらはランダムアクセスは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)

append, pop

この辺は 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

この辺も 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() とか
    • 未実装 (実装するとしたらO(N) かな)
      • listに変換するのもO(N)っぽいので困らなそう
  • rotate() とか
    • 未実装 (実装するとしたらO(1) かな)
      • いる?
  • エラーハンドリングが甘いですけど
    • よしなに使ってください

ところで

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

thanks

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


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