5.11.1 レシピ

この節では deque をつかったさまざまなアプローチを紹介します。

rotate() メソッドのおかげで、 deque の一部を切り出したり削除したりできることになります。たとえば del d[n] の純粋な Python 実装では pop したい要素まで rotate() します :

def delete_nth(d, n):
    d.rotate(-n)
    d.popleft()
    d.rotate(n)

deque の切り出しを実装するのにも、同様のアプローチを使います。まず対象となる要素を rotate() によって deque の左端までもってきてから、popleft() をつかって古い要素を消します。そして、extend() で新しい要素を追加したのち、逆のローテートでもとに戻せばよいのです。

このアプローチをやや変えたものとして、Forth スタイルのスタック操作、つまり dup, drop, swap, over, pick, rot, および roll を実装するのも簡単です。

ラウンドロビンのタスクサーバは deque をつかって、 popleft() で現在のタスクを選択し、入力ストリームが使い果たされなければ append() でタスクリストの戻してやることができます:

def roundrobin(*iterables):
    pending = deque(iter(i) for i in iterables)
    while pending:
        task = pending.popleft()
        try:
            yield task.next()
        except StopIteration:
            continue
        pending.append(task)

>>> for value in roundrobin('abc', 'd', 'efgh'):
...     print value

a
d
e
b
f
c
g
h

複数パスのデータ・リダクションアルゴリズムは、popleft() を複数回呼んで要素をとりだし、リダクション用の関数を適用してから append() で deque に戻してやることにより、簡潔かつ効率的に表現することができます。

たとえば入れ子状になったリストでバランスされた二進木をつくりたい場合、 2つの隣接するノードをひとつのリストにグループ化することになります:

def maketree(iterable):
    d = deque(iterable)
    while len(d) > 1:
        pair = [d.popleft(), d.popleft()]
        d.append(pair)
    return list(d)

>>> print maketree('abcdefgh')
[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]