5.3.1.1 Recipes
This section shows various approaches to working with deques.
The rotate() method provides a way to implement deque
slicing and deletion. For example, a pure python implementation of
del d[n] relies on the rotate() method to position
elements to be popped:
def delete_nth(d, n):
d.rotate(-n)
d.popleft()
d.rotate(n)
To implement deque slicing, use a similar approach applying
rotate() to bring a target element to the left side of the deque.
Remove old entries with popleft(), add new entries with
extend(), and then reverse the rotation.
With minor variations on that approach, it is easy to implement Forth style
stack manipulations such as dup , drop , swap , over ,
pick , rot , and roll .
A roundrobin task server can be built from a deque using
popleft() to select the current task and append()
to add it back to the tasklist if the input stream is not exhausted:
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
Multi-pass data reduction algorithms can be succinctly expressed and
efficiently coded by extracting elements with multiple calls to
popleft(), applying the reduction function, and calling
append() to add the result back to the queue.
For example, building a balanced binary tree of nested lists entails
reducing two adjacent nodes into one by grouping them in a list:
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']]]]
Release 2.5.2, documentation updated on 21st February, 2008.
See About this document... for information on suggesting changes.
|