この節では 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']]]]