さいきんは暇なときにPythonの標準のライブラリのことを調べています。

Pythonは豊富なサードパーティライブラリがあってimportするだけで色々なことができるわけですが、標準のライブラリも知っておいて損はありません。

今回はcollections.dequeについてまとめていきます。

参考ページ

https://docs.python.org/ja/3/library/collections.html

使い方

イテラブルを引数にしてdequeオブジェクトを作れます。

from collections import deque

l = [10, 20, 30]
d = deque(l)
print(d)
>>>
deque([10, 20, 30])

メソッド

一部を紹介します。

要素を末尾に加える

d.append(40)
print(d)
>>>
deque([10, 20, 30, 40])

これはリストと同じですね。

要素を先頭に加える

d.appendleft(0)
print(d)
>>>
deque([0, 10, 20, 30, 40])

リストの場合は先頭に加えるときはinsert(0,要素)とします。

dequeオブジェクトだと直感的ですね。

イテラブルの追加

d.extend([50, 60, 70])
d.extendleft([-10, -20, -30])
print(d)
>>>
deque([-30, -20, -10, 0, 10, 20, 30, 40, 50, 60, 70])

要素の取り出し

pop()で最後の要素を返して排除、popleft()で最初の要素を返して排除します。

print(d)
last=d.pop()
print(last,d)
first=d.popleft()
print(first,d)
>>>
deque([-30, -20, -10, 0, 10, 20, 30, 40, 50, 60, 70])
70 deque([-30, -20, -10, 0, 10, 20, 30, 40, 50, 60])
-30 deque([-20, -10, 0, 10, 20, 30, 40, 50, 60])

要素をずらす

これがリストにない機能で面白いです。

d.rotate(1)
print(d)
d.rotate(-2)
print(d)
>>>
deque([70, -30, -20, -10, 0, 10, 20, 30, 40, 50, 60])
deque([-20, -10, 0, 10, 20, 30, 40, 50, 60, 70, -30])

ベルトコンベアのように、指定した数だけ位置をずらせます。

正の値を与えれば右に、負の値を与えれば左にずれていくイメージです。

最大長の指定

インスタンス化する際にmaxlenを指定すると固定長になります。

最大長を超える分は自動で排除されます。

iterable = [10, 20, 30]
d = deque(iterable, maxlen=3)
print(d)
d.appendleft(0)
print(d)
>>>
deque([10, 20, 30], maxlen=3)
deque([0, 10, 20], maxlen=3)

使いどころ、使用例

パフォーマンスについて、通常のリストでは末尾に値を追加する際はO(1)で行えますが、先頭に追加する際は、O(N)かかります。

配列が大きいと比例して時間が増えていくイメージです。

対してdequeは先頭と末尾の追加について、O(1)で行えます。配列の大きさに影響なく要素を追加できます。

要素の削除についても同様です。

とはいえdequeにも弱点がありまして、たとえば要素にアクセスする際は線形時間がかかります。

リストだと配列が大きくてもO(1)です。

なので、配列の両端に関してなんやかんやするプログラムを組む時にdequeを使うと良いでしょう。

（このような性質から両端キューとも呼ばれます）

リングメニュープログラム

他にはrotateメソッドが面白そうで、ゲームのリングメニューっぽい感じがありますよね。

こういうやつですね。

それっぽいものを簡易的に作ってみました。

from collections import deque


class RingMenu:

    def __init__(self):
        self.jobs = deque(['見習い戦士', 'ナイト', 'モンク', '黒魔導士', '白魔導士'])

    def cur_right(self):
        self.jobs.rotate(1)

    def cur_left(self):
        self.jobs.rotate(-1)

    def display(self):
        selected = f'**{self.jobs[0]}**'
        print(selected.center(20))
        print()
        print(self.jobs[4].ljust(10) + self.jobs[1].rjust(10))
        print()
        print(self.jobs[3].rjust(8) + '  ' + self.jobs[2].ljust(8))

カーソル操作に合わせて表示を切り替えるクラスです。

動作を確認してみましょう。

menu = RingMenu()
menu.display()
>>>
     **見習い戦士**      


白魔導士             ナイト


    黒魔導士  モンク     

このように見習い戦士が選択されています。

カーソルを右に一つずらします。

menu.cur_right()
menu.display()
>>>
      **白魔導士**      


黒魔導士           見習い戦士


     モンク  ナイト     

リングが右に回りました。

次に左に回してみましょう。

menu.cur_right()
menu.cur_left()
menu.cur_left()
menu.display()
>>>
      **ナイト**       


見習い戦士            モンク


    白魔導士  黒魔導士

麻雀プログラム

dequeと書いてデックと読むらしいのですが、ゲームの山とかデッキの実装と相性が良いんだと思います。

試しに麻雀っぽいプログラムを組んでみました。

class MahjongPai:
    MANZU = [('m', i) for i in range(1, 10)] * 4
    SOZU = [('s', i) for i in range(1, 10)] * 4
    PINZU = [('p', i) for i in range(1, 10)] * 4
    ZIHAI = [('z', i) for i in range(1, 8)] * 4
    ALL_PAI = MANZU + SOZU + PINZU + ZIHAI


class Yama:

    def __init__(self):
        self.yama = deque(MahjongPai().ALL_PAI)
        random.shuffle(self.yama)
        self.wan_pai = None

    def set_wan_pai(self):
        """王牌をセットする"""
        d = deque()
        for i in range(1, 15):
            pai = self.yama.popleft()
            d.append(pai)
        self.wan_pai = d

    def dist_haipai(self):
        """配牌する"""
        haipai = deque()
        for i in range(1, 14):
            pai = self.yama.popleft()
            haipai.append(pai)
        return haipai

    def dist_tsumo(self):
        """ツモ牌を配る"""
        return self.yama.popleft()


class Janshi:

    def __init__(self, name):
        self.name = name
        self.tehai = None

    def get_haipai(self, haipai):
        """配牌を得る"""
        # dequeオブジェクトだとsortが使えないので手配はリスト
        self.tehai = list(haipai)

    def tsumo(self, pai):
        """ツモする"""
        self.tehai.insert(0, pai)

    def dahai(self, index):
        """打牌する"""
        pai = self.tehai[index]
        self.tehai.remove(pai)

    def ri_pai(self):
        """理牌する"""
        self.tehai.sort(key=lambda x: (x[0], x[1]))

これはこのように遊びます。

yama = Yama()
yama.set_wan_pai()
tetsuya = Janshi('asada_tetsuya')
tetsuya.get_haipai(yama.dist_haipai())
tetsuya.ri_pai()
print("**配牌の表示**")
print(tetsuya.tehai)
print("**ツモした後の手配**")
tetsuya.tsumo(yama.dist_tsumo())
print(tetsuya.tehai)
print("**一番左の牌を打牌**")
tetsuya.dahai(1)
print(tetsuya.tehai)

**配牌の表示**
[('m', 5), ('m', 5), ('m', 7), ('p', 1), ('p', 5), ('p', 6), ('p', 7), ('s', 3), ('s', 3), ('s', 6), ('s', 7), ('z', 5), ('z', 7)]
**ツモした後の手配**
[('m', 8), ('m', 5), ('m', 5), ('m', 7), ('p', 1), ('p', 5), ('p', 6), ('p', 7), ('s', 3), ('s', 3), ('s', 6), ('s', 7), ('z', 5), ('z', 7)]
**一番左の牌を打牌**
[('m', 8), ('m', 5), ('m', 7), ('p', 1), ('p', 5), ('p', 6), ('p', 7), ('s', 3), ('s', 3), ('s', 6), ('s', 7), ('z', 5), ('z', 7)]

以上、dequeについての記事でした。