Navigation

Deque

両端キューまたは deque は両端から要素の追加や削除をサポートします。一般的に使用されるスタックやキューはその入出力を1つの終端のみに制限するように deque を退化させたものです。

import collections

d = collections.deque('abcdefg')
print 'Deque:', d
print 'Length:', len(d)
print 'Left end:', d[0]
print 'Right end:', d[-1]

d.remove('c')
print 'remove(c):', d

deque はシーケンス型のコンテナなので、 __getitem__() でコンテンツを調べる、長さを決定する、識別子でマッチした中間の要素を削除するといったリストがサポートする操作のいくつかをサポートします。

$ python collections_deque.py
Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
Length: 7
Left end: a
Right end: g
remove(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])

追加

deque は Python 実装では “左側” や “右側” と呼びどちらかの一端から追加されます。

import collections

# 右側に追加
d = collections.deque()
d.extend('abcdefg')
print 'extend    :', d
d.append('h')
print 'append    :', d

# 左側に追加
d = collections.deque()
d.extendleft('abcdefg')
print 'extendleft:', d
d.appendleft('h')
print 'appendleft:', d

extendleft() は入力シーケンスを処理することと、各要素に appendleft() を実行することは等価であることに注意してください。最終結果はその入力シーケンスを逆順に含んだ deque になります。

$ python collections_deque_populating.py
extend    : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
append    : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
extendleft: deque(['g', 'f', 'e', 'd', 'c', 'b', 'a'])
appendleft: deque(['h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'])

消費

同様に deque の要素は適用されるアルゴリズム次第で両端か、どちらか一方の端から消費されます。

import collections

print 'From the right:'
d = collections.deque('abcdefg')
while True:
    try:
        print d.pop()
    except IndexError:
        break

print '\nFrom the left:'
d = collections.deque('abcdefg')
while True:
    try:
        print d.popleft()
    except IndexError:
        break

deque の “右側” から要素を取り出すには pop() を、”左側” から取り出すには popleft() を使用してください。

$ python collections_deque_consuming.py
From the right:
g
f
e
d
c
b
a

From the left:
a
b
c
d
e
f
g

deque はスレッドセーフなので、そのコンテンツは別々のスレッドで同時に両端から消費されても大丈夫です。

import collections
import threading
import time

candle = collections.deque(xrange(11))

def burn(direction, nextSource):
    while True:
        try:
            next = nextSource()
        except IndexError:
            break
        else:
            print '%8s: %s' % (direction, next)
            time.sleep(0.1)
    print '%8s done' % direction
    return

left = threading.Thread(target=burn, args=('Left', candle.popleft))
right = threading.Thread(target=burn, args=('Right', candle.pop))

left.start()
right.start()

left.join()
right.join()

このサンプルのスレッドは deque が空になるまで両端から交互に要素を削除します。

$ python collections_deque_both_ends.py
    Left: 0
   Right: 10
    Left: 1
   Right: 9
    Left: 2
   Right: 8
    Left: 3
   Right: 7
   Right: 6
    Left: 4
    Left: 5
    Right done
    Left done

ローテート

別の deque の便利な機能は要素を読み飛ばすために一方の端へローテートすることです。

import collections

d = collections.deque(xrange(10))
print 'Normal        :', d

d = collections.deque(xrange(10))
d.rotate(2)
print 'Right rotation:', d

d = collections.deque(xrange(10))
d.rotate(-2)
print 'Left rotation :', d

deque を(正のローテーションを使用して)右端へローテートすると、右端から要素を取り出して左端へその取り出した要素を移動します。(負の値で)左端へローテートすると、左端から要素を取り出して右端へその取り出した要素を移動します。それは目盛盤の端を刻み込むように deque の要素を視覚化する助けになるかもしれません。

$ python collections_deque_rotate.py
Normal        : deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
Right rotation: deque([8, 9, 0, 1, 2, 3, 4, 5, 6, 7])
Left rotation : deque([2, 3, 4, 5, 6, 7, 8, 9, 0, 1])

See also

WikiPedia: Deque
deque データ構造の説明
Deque Recipes
標準ライブラリドキュメントの deque を使用するアルゴリズムのサンプル

Navigation

Bookmark and Share