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']]]]
ご意見やご指摘をお寄せになりたい方は、 このドキュメントについて... をご覧ください。