[Python-checkins] r86919 - python/branches/py3k/Doc/library/itertools.rst
raymond.hettinger
python-checkins at python.org
Wed Dec 1 23:50:36 CET 2010
Author: raymond.hettinger
Date: Wed Dec 1 23:50:36 2010
New Revision: 86919
Log:
Add itertools.accumulate().
Modified:
python/branches/py3k/Doc/library/itertools.rst
Modified: python/branches/py3k/Doc/library/itertools.rst
==============================================================================
--- python/branches/py3k/Doc/library/itertools.rst (original)
+++ python/branches/py3k/Doc/library/itertools.rst Wed Dec 1 23:50:36 2010
@@ -2,14 +2,14 @@
=======================================================================
.. module:: itertools
- :synopsis: Functions creating iterators for efficient looping.
+ :synopsis: Functions creating iterators for efficient looping.
.. moduleauthor:: Raymond Hettinger <python at rcn.com>
.. sectionauthor:: Raymond Hettinger <python at rcn.com>
.. testsetup::
- from itertools import *
+ from itertools import *
This module implements a number of :term:`iterator` building blocks inspired
@@ -46,6 +46,7 @@
==================== ============================ ================================================= =============================================================
Iterator Arguments Results Example
==================== ============================ ================================================= =============================================================
+:func:`accumulate` p[, start=0] p0, p0+p1, p0+p1+p2 ... ` ``accumulate([1,2,3,4,5]) --> 1 3 6 10 15``
:func:`chain` p, q, ... p0, p1, ... plast, q0, q1, ... ``chain('ABC', 'DEF') --> A B C D E F``
:func:`compress` data, selectors (d[0] if s[0]), (d[1] if s[1]), ... ``compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F``
:func:`dropwhile` pred, seq seq[n], seq[n+1], starting when pred fails ``dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1``
@@ -83,47 +84,62 @@
streams of infinite length, so they should only be accessed by functions or
loops that truncate the stream.
+.. function:: accumulate(iterable, start=0)
+
+ Make an iterator that returns accumulated sums plus the value of the *start*
+ parameter (which defaults to :const:`0`). Elements may be any addable type
+ including :class:`Decimal` or :class:`Fraction`. Equivalent to::
+
+ def accumulate(iterable, start=0):
+ 'Return running totals'
+ # accumulate([1,2,3,4,5]) --> 1 3 6 10 15
+ total = start
+ for element in iterable:
+ total += element
+ yield total
+
+ .. versionadded:: 3.2
.. function:: chain(*iterables)
- Make an iterator that returns elements from the first iterable until it is
- exhausted, then proceeds to the next iterable, until all of the iterables are
- exhausted. Used for treating consecutive sequences as a single sequence.
- Equivalent to::
-
- def chain(*iterables):
- # chain('ABC', 'DEF') --> A B C D E F
- for it in iterables:
- for element in it:
- yield element
+ Make an iterator that returns elements from the first iterable until it is
+ exhausted, then proceeds to the next iterable, until all of the iterables are
+ exhausted. Used for treating consecutive sequences as a single sequence.
+ Equivalent to::
+
+ def chain(*iterables):
+ # chain('ABC', 'DEF') --> A B C D E F
+ for it in iterables:
+ for element in it:
+ yield element
.. classmethod:: chain.from_iterable(iterable)
- Alternate constructor for :func:`chain`. Gets chained inputs from a
- single iterable argument that is evaluated lazily. Equivalent to::
+ Alternate constructor for :func:`chain`. Gets chained inputs from a
+ single iterable argument that is evaluated lazily. Equivalent to::
- @classmethod
- def from_iterable(iterables):
- # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F
- for it in iterables:
- for element in it:
- yield element
+ @classmethod
+ def from_iterable(iterables):
+ # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F
+ for it in iterables:
+ for element in it:
+ yield element
.. function:: combinations(iterable, r)
- Return *r* length subsequences of elements from the input *iterable*.
+ Return *r* length subsequences of elements from the input *iterable*.
- Combinations are emitted in lexicographic sort order. So, if the
- input *iterable* is sorted, the combination tuples will be produced
- in sorted order.
+ Combinations are emitted in lexicographic sort order. So, if the
+ input *iterable* is sorted, the combination tuples will be produced
+ in sorted order.
- Elements are treated as unique based on their position, not on their
- value. So if the input elements are unique, there will be no repeat
- values in each combination.
+ Elements are treated as unique based on their position, not on their
+ value. So if the input elements are unique, there will be no repeat
+ values in each combination.
- Equivalent to::
+ Equivalent to::
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
@@ -145,9 +161,9 @@
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
- The code for :func:`combinations` can be also expressed as a subsequence
- of :func:`permutations` after filtering entries where the elements are not
- in sorted order (according to their position in the input pool)::
+ The code for :func:`combinations` can be also expressed as a subsequence
+ of :func:`permutations` after filtering entries where the elements are not
+ in sorted order (according to their position in the input pool)::
def combinations(iterable, r):
pool = tuple(iterable)
@@ -156,23 +172,23 @@
if sorted(indices) == list(indices):
yield tuple(pool[i] for i in indices)
- The number of items returned is ``n! / r! / (n-r)!`` when ``0 <= r <= n``
- or zero when ``r > n``.
+ The number of items returned is ``n! / r! / (n-r)!`` when ``0 <= r <= n``
+ or zero when ``r > n``.
.. function:: combinations_with_replacement(iterable, r)
- Return *r* length subsequences of elements from the input *iterable*
- allowing individual elements to be repeated more than once.
+ Return *r* length subsequences of elements from the input *iterable*
+ allowing individual elements to be repeated more than once.
- Combinations are emitted in lexicographic sort order. So, if the
- input *iterable* is sorted, the combination tuples will be produced
- in sorted order.
-
- Elements are treated as unique based on their position, not on their
- value. So if the input elements are unique, the generated combinations
- will also be unique.
+ Combinations are emitted in lexicographic sort order. So, if the
+ input *iterable* is sorted, the combination tuples will be produced
+ in sorted order.
+
+ Elements are treated as unique based on their position, not on their
+ value. So if the input elements are unique, the generated combinations
+ will also be unique.
- Equivalent to::
+ Equivalent to::
def combinations_with_replacement(iterable, r):
# combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
@@ -191,9 +207,9 @@
indices[i:] = [indices[i] + 1] * (r - i)
yield tuple(pool[i] for i in indices)
- The code for :func:`combinations_with_replacement` can be also expressed as
- a subsequence of :func:`product` after filtering entries where the elements
- are not in sorted order (according to their position in the input pool)::
+ The code for :func:`combinations_with_replacement` can be also expressed as
+ a subsequence of :func:`product` after filtering entries where the elements
+ are not in sorted order (according to their position in the input pool)::
def combinations_with_replacement(iterable, r):
pool = tuple(iterable)
@@ -202,196 +218,196 @@
if sorted(indices) == list(indices):
yield tuple(pool[i] for i in indices)
- The number of items returned is ``(n+r-1)! / r! / (n-1)!`` when ``n > 0``.
+ The number of items returned is ``(n+r-1)! / r! / (n-1)!`` when ``n > 0``.
- .. versionadded:: 3.1
+ .. versionadded:: 3.1
.. function:: compress(data, selectors)
- Make an iterator that filters elements from *data* returning only those that
- have a corresponding element in *selectors* that evaluates to ``True``.
- Stops when either the *data* or *selectors* iterables has been exhausted.
- Equivalent to::
-
- def compress(data, selectors):
- # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
- return (d for d, s in zip(data, selectors) if s)
+ Make an iterator that filters elements from *data* returning only those that
+ have a corresponding element in *selectors* that evaluates to ``True``.
+ Stops when either the *data* or *selectors* iterables has been exhausted.
+ Equivalent to::
+
+ def compress(data, selectors):
+ # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
+ return (d for d, s in zip(data, selectors) if s)
- .. versionadded:: 3.1
+ .. versionadded:: 3.1
.. function:: count(start=0, step=1)
- Make an iterator that returns evenly spaced values starting with *n*. Often
- used as an argument to :func:`map` to generate consecutive data points.
- Also, used with :func:`zip` to add sequence numbers. Equivalent to::
-
- def count(start=0, step=1):
- # count(10) --> 10 11 12 13 14 ...
- # count(2.5, 0.5) -> 3.5 3.0 4.5 ...
- n = start
- while True:
- yield n
- n += step
-
- When counting with floating point numbers, better accuracy can sometimes be
- achieved by substituting multiplicative code such as: ``(start + step * i
- for i in count())``.
+ Make an iterator that returns evenly spaced values starting with *n*. Often
+ used as an argument to :func:`map` to generate consecutive data points.
+ Also, used with :func:`zip` to add sequence numbers. Equivalent to::
+
+ def count(start=0, step=1):
+ # count(10) --> 10 11 12 13 14 ...
+ # count(2.5, 0.5) -> 3.5 3.0 4.5 ...
+ n = start
+ while True:
+ yield n
+ n += step
+
+ When counting with floating point numbers, better accuracy can sometimes be
+ achieved by substituting multiplicative code such as: ``(start + step * i
+ for i in count())``.
- .. versionchanged:: 3.1
- Added *step* argument and allowed non-integer arguments.
+ .. versionchanged:: 3.1
+ Added *step* argument and allowed non-integer arguments.
.. function:: cycle(iterable)
- Make an iterator returning elements from the iterable and saving a copy of each.
- When the iterable is exhausted, return elements from the saved copy. Repeats
- indefinitely. Equivalent to::
-
- def cycle(iterable):
- # cycle('ABCD') --> A B C D A B C D A B C D ...
- saved = []
- for element in iterable:
- yield element
- saved.append(element)
- while saved:
- for element in saved:
+ Make an iterator returning elements from the iterable and saving a copy of each.
+ When the iterable is exhausted, return elements from the saved copy. Repeats
+ indefinitely. Equivalent to::
+
+ def cycle(iterable):
+ # cycle('ABCD') --> A B C D A B C D A B C D ...
+ saved = []
+ for element in iterable:
+ yield element
+ saved.append(element)
+ while saved:
+ for element in saved:
yield element
- Note, this member of the toolkit may require significant auxiliary storage
- (depending on the length of the iterable).
+ Note, this member of the toolkit may require significant auxiliary storage
+ (depending on the length of the iterable).
.. function:: dropwhile(predicate, iterable)
- Make an iterator that drops elements from the iterable as long as the predicate
- is true; afterwards, returns every element. Note, the iterator does not produce
- *any* output until the predicate first becomes false, so it may have a lengthy
- start-up time. Equivalent to::
-
- def dropwhile(predicate, iterable):
- # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1
- iterable = iter(iterable)
- for x in iterable:
- if not predicate(x):
- yield x
- break
- for x in iterable:
- yield x
+ Make an iterator that drops elements from the iterable as long as the predicate
+ is true; afterwards, returns every element. Note, the iterator does not produce
+ *any* output until the predicate first becomes false, so it may have a lengthy
+ start-up time. Equivalent to::
+
+ def dropwhile(predicate, iterable):
+ # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1
+ iterable = iter(iterable)
+ for x in iterable:
+ if not predicate(x):
+ yield x
+ break
+ for x in iterable:
+ yield x
.. function:: filterfalse(predicate, iterable)
- Make an iterator that filters elements from iterable returning only those for
- which the predicate is ``False``. If *predicate* is ``None``, return the items
- that are false. Equivalent to::
-
- def filterfalse(predicate, iterable):
- # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8
- if predicate is None:
- predicate = bool
- for x in iterable:
- if not predicate(x):
- yield x
+ Make an iterator that filters elements from iterable returning only those for
+ which the predicate is ``False``. If *predicate* is ``None``, return the items
+ that are false. Equivalent to::
+
+ def filterfalse(predicate, iterable):
+ # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8
+ if predicate is None:
+ predicate = bool
+ for x in iterable:
+ if not predicate(x):
+ yield x
.. function:: groupby(iterable, key=None)
- Make an iterator that returns consecutive keys and groups from the *iterable*.
- The *key* is a function computing a key value for each element. If not
- specified or is ``None``, *key* defaults to an identity function and returns
- the element unchanged. Generally, the iterable needs to already be sorted on
- the same key function.
-
- The operation of :func:`groupby` is similar to the ``uniq`` filter in Unix. It
- generates a break or new group every time the value of the key function changes
- (which is why it is usually necessary to have sorted the data using the same key
- function). That behavior differs from SQL's GROUP BY which aggregates common
- elements regardless of their input order.
-
- The returned group is itself an iterator that shares the underlying iterable
- with :func:`groupby`. Because the source is shared, when the :func:`groupby`
- object is advanced, the previous group is no longer visible. So, if that data
- is needed later, it should be stored as a list::
-
- groups = []
- uniquekeys = []
- data = sorted(data, key=keyfunc)
- for k, g in groupby(data, keyfunc):
- groups.append(list(g)) # Store group iterator as a list
- uniquekeys.append(k)
-
- :func:`groupby` is equivalent to::
-
- class groupby:
- # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
- # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D
- def __init__(self, iterable, key=None):
- if key is None:
- key = lambda x: x
- self.keyfunc = key
- self.it = iter(iterable)
- self.tgtkey = self.currkey = self.currvalue = object()
- def __iter__(self):
- return self
- def __next__(self):
- while self.currkey == self.tgtkey:
- self.currvalue = next(self.it) # Exit on StopIteration
- self.currkey = self.keyfunc(self.currvalue)
- self.tgtkey = self.currkey
- return (self.currkey, self._grouper(self.tgtkey))
- def _grouper(self, tgtkey):
- while self.currkey == tgtkey:
- yield self.currvalue
- self.currvalue = next(self.it) # Exit on StopIteration
- self.currkey = self.keyfunc(self.currvalue)
+ Make an iterator that returns consecutive keys and groups from the *iterable*.
+ The *key* is a function computing a key value for each element. If not
+ specified or is ``None``, *key* defaults to an identity function and returns
+ the element unchanged. Generally, the iterable needs to already be sorted on
+ the same key function.
+
+ The operation of :func:`groupby` is similar to the ``uniq`` filter in Unix. It
+ generates a break or new group every time the value of the key function changes
+ (which is why it is usually necessary to have sorted the data using the same key
+ function). That behavior differs from SQL's GROUP BY which aggregates common
+ elements regardless of their input order.
+
+ The returned group is itself an iterator that shares the underlying iterable
+ with :func:`groupby`. Because the source is shared, when the :func:`groupby`
+ object is advanced, the previous group is no longer visible. So, if that data
+ is needed later, it should be stored as a list::
+
+ groups = []
+ uniquekeys = []
+ data = sorted(data, key=keyfunc)
+ for k, g in groupby(data, keyfunc):
+ groups.append(list(g)) # Store group iterator as a list
+ uniquekeys.append(k)
+
+ :func:`groupby` is equivalent to::
+
+ class groupby:
+ # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
+ # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D
+ def __init__(self, iterable, key=None):
+ if key is None:
+ key = lambda x: x
+ self.keyfunc = key
+ self.it = iter(iterable)
+ self.tgtkey = self.currkey = self.currvalue = object()
+ def __iter__(self):
+ return self
+ def __next__(self):
+ while self.currkey == self.tgtkey:
+ self.currvalue = next(self.it) # Exit on StopIteration
+ self.currkey = self.keyfunc(self.currvalue)
+ self.tgtkey = self.currkey
+ return (self.currkey, self._grouper(self.tgtkey))
+ def _grouper(self, tgtkey):
+ while self.currkey == tgtkey:
+ yield self.currvalue
+ self.currvalue = next(self.it) # Exit on StopIteration
+ self.currkey = self.keyfunc(self.currvalue)
.. function:: islice(iterable, [start,] stop [, step])
- Make an iterator that returns selected elements from the iterable. If *start* is
- non-zero, then elements from the iterable are skipped until start is reached.
- Afterward, elements are returned consecutively unless *step* is set higher than
- one which results in items being skipped. If *stop* is ``None``, then iteration
- continues until the iterator is exhausted, if at all; otherwise, it stops at the
- specified position. Unlike regular slicing, :func:`islice` does not support
- negative values for *start*, *stop*, or *step*. Can be used to extract related
- fields from data where the internal structure has been flattened (for example, a
- multi-line report may list a name field on every third line). Equivalent to::
-
- def islice(iterable, *args):
- # islice('ABCDEFG', 2) --> A B
- # islice('ABCDEFG', 2, 4) --> C D
- # islice('ABCDEFG', 2, None) --> C D E F G
- # islice('ABCDEFG', 0, None, 2) --> A C E G
- s = slice(*args)
- it = iter(range(s.start or 0, s.stop or sys.maxsize, s.step or 1))
- nexti = next(it)
- for i, element in enumerate(iterable):
- if i == nexti:
- yield element
- nexti = next(it)
+ Make an iterator that returns selected elements from the iterable. If *start* is
+ non-zero, then elements from the iterable are skipped until start is reached.
+ Afterward, elements are returned consecutively unless *step* is set higher than
+ one which results in items being skipped. If *stop* is ``None``, then iteration
+ continues until the iterator is exhausted, if at all; otherwise, it stops at the
+ specified position. Unlike regular slicing, :func:`islice` does not support
+ negative values for *start*, *stop*, or *step*. Can be used to extract related
+ fields from data where the internal structure has been flattened (for example, a
+ multi-line report may list a name field on every third line). Equivalent to::
+
+ def islice(iterable, *args):
+ # islice('ABCDEFG', 2) --> A B
+ # islice('ABCDEFG', 2, 4) --> C D
+ # islice('ABCDEFG', 2, None) --> C D E F G
+ # islice('ABCDEFG', 0, None, 2) --> A C E G
+ s = slice(*args)
+ it = iter(range(s.start or 0, s.stop or sys.maxsize, s.step or 1))
+ nexti = next(it)
+ for i, element in enumerate(iterable):
+ if i == nexti:
+ yield element
+ nexti = next(it)
- If *start* is ``None``, then iteration starts at zero. If *step* is ``None``,
- then the step defaults to one.
+ If *start* is ``None``, then iteration starts at zero. If *step* is ``None``,
+ then the step defaults to one.
.. function:: permutations(iterable, r=None)
- Return successive *r* length permutations of elements in the *iterable*.
+ Return successive *r* length permutations of elements in the *iterable*.
- If *r* is not specified or is ``None``, then *r* defaults to the length
- of the *iterable* and all possible full-length permutations
- are generated.
+ If *r* is not specified or is ``None``, then *r* defaults to the length
+ of the *iterable* and all possible full-length permutations
+ are generated.
- Permutations are emitted in lexicographic sort order. So, if the
- input *iterable* is sorted, the permutation tuples will be produced
- in sorted order.
+ Permutations are emitted in lexicographic sort order. So, if the
+ input *iterable* is sorted, the permutation tuples will be produced
+ in sorted order.
- Elements are treated as unique based on their position, not on their
- value. So if the input elements are unique, there will be no repeat
- values in each permutation.
+ Elements are treated as unique based on their position, not on their
+ value. So if the input elements are unique, there will be no repeat
+ values in each permutation.
- Equivalent to::
+ Equivalent to::
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
@@ -418,9 +434,9 @@
else:
return
- The code for :func:`permutations` can be also expressed as a subsequence of
- :func:`product`, filtered to exclude entries with repeated elements (those
- from the same position in the input pool)::
+ The code for :func:`permutations` can be also expressed as a subsequence of
+ :func:`product`, filtered to exclude entries with repeated elements (those
+ from the same position in the input pool)::
def permutations(iterable, r=None):
pool = tuple(iterable)
@@ -430,87 +446,87 @@
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)
- The number of items returned is ``n! / (n-r)!`` when ``0 <= r <= n``
- or zero when ``r > n``.
+ The number of items returned is ``n! / (n-r)!`` when ``0 <= r <= n``
+ or zero when ``r > n``.
.. function:: product(*iterables, repeat=1)
- Cartesian product of input iterables.
+ Cartesian product of input iterables.
- Equivalent to nested for-loops in a generator expression. For example,
- ``product(A, B)`` returns the same as ``((x,y) for x in A for y in B)``.
+ Equivalent to nested for-loops in a generator expression. For example,
+ ``product(A, B)`` returns the same as ``((x,y) for x in A for y in B)``.
- The nested loops cycle like an odometer with the rightmost element advancing
- on every iteration. This pattern creates a lexicographic ordering so that if
- the input's iterables are sorted, the product tuples are emitted in sorted
- order.
-
- To compute the product of an iterable with itself, specify the number of
- repetitions with the optional *repeat* keyword argument. For example,
- ``product(A, repeat=4)`` means the same as ``product(A, A, A, A)``.
-
- This function is equivalent to the following code, except that the
- actual implementation does not build up intermediate results in memory::
-
- def product(*args, repeat=1):
- # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
- # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
- pools = [tuple(pool) for pool in args] * repeat
- result = [[]]
- for pool in pools:
- result = [x+[y] for x in result for y in pool]
- for prod in result:
- yield tuple(prod)
+ The nested loops cycle like an odometer with the rightmost element advancing
+ on every iteration. This pattern creates a lexicographic ordering so that if
+ the input's iterables are sorted, the product tuples are emitted in sorted
+ order.
+
+ To compute the product of an iterable with itself, specify the number of
+ repetitions with the optional *repeat* keyword argument. For example,
+ ``product(A, repeat=4)`` means the same as ``product(A, A, A, A)``.
+
+ This function is equivalent to the following code, except that the
+ actual implementation does not build up intermediate results in memory::
+
+ def product(*args, repeat=1):
+ # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
+ # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
+ pools = [tuple(pool) for pool in args] * repeat
+ result = [[]]
+ for pool in pools:
+ result = [x+[y] for x in result for y in pool]
+ for prod in result:
+ yield tuple(prod)
.. function:: repeat(object[, times])
- Make an iterator that returns *object* over and over again. Runs indefinitely
- unless the *times* argument is specified. Used as argument to :func:`map` for
- invariant parameters to the called function. Also used with :func:`zip` to
- create an invariant part of a tuple record. Equivalent to::
-
- def repeat(object, times=None):
- # repeat(10, 3) --> 10 10 10
- if times is None:
- while True:
- yield object
- else:
- for i in range(times):
- yield object
+ Make an iterator that returns *object* over and over again. Runs indefinitely
+ unless the *times* argument is specified. Used as argument to :func:`map` for
+ invariant parameters to the called function. Also used with :func:`zip` to
+ create an invariant part of a tuple record. Equivalent to::
+
+ def repeat(object, times=None):
+ # repeat(10, 3) --> 10 10 10
+ if times is None:
+ while True:
+ yield object
+ else:
+ for i in range(times):
+ yield object
.. function:: starmap(function, iterable)
- Make an iterator that computes the function using arguments obtained from
- the iterable. Used instead of :func:`map` when argument parameters are already
- grouped in tuples from a single iterable (the data has been "pre-zipped"). The
- difference between :func:`map` and :func:`starmap` parallels the distinction
- between ``function(a,b)`` and ``function(*c)``. Equivalent to::
-
- def starmap(function, iterable):
- # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
- for args in iterable:
- yield function(*args)
+ Make an iterator that computes the function using arguments obtained from
+ the iterable. Used instead of :func:`map` when argument parameters are already
+ grouped in tuples from a single iterable (the data has been "pre-zipped"). The
+ difference between :func:`map` and :func:`starmap` parallels the distinction
+ between ``function(a,b)`` and ``function(*c)``. Equivalent to::
+
+ def starmap(function, iterable):
+ # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
+ for args in iterable:
+ yield function(*args)
.. function:: takewhile(predicate, iterable)
- Make an iterator that returns elements from the iterable as long as the
- predicate is true. Equivalent to::
+ Make an iterator that returns elements from the iterable as long as the
+ predicate is true. Equivalent to::
- def takewhile(predicate, iterable):
- # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
- for x in iterable:
- if predicate(x):
- yield x
- else:
- break
+ def takewhile(predicate, iterable):
+ # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
+ for x in iterable:
+ if predicate(x):
+ yield x
+ else:
+ break
.. function:: tee(iterable, n=2)
- Return *n* independent iterators from a single iterable. Equivalent to::
+ Return *n* independent iterators from a single iterable. Equivalent to::
def tee(iterable, n=2):
it = iter(iterable)
@@ -524,38 +540,38 @@
yield mydeque.popleft()
return tuple(gen(d) for d in deques)
- Once :func:`tee` has made a split, the original *iterable* should not be
- used anywhere else; otherwise, the *iterable* could get advanced without
- the tee objects being informed.
-
- This itertool may require significant auxiliary storage (depending on how
- much temporary data needs to be stored). In general, if one iterator uses
- most or all of the data before another iterator starts, it is faster to use
- :func:`list` instead of :func:`tee`.
+ Once :func:`tee` has made a split, the original *iterable* should not be
+ used anywhere else; otherwise, the *iterable* could get advanced without
+ the tee objects being informed.
+
+ This itertool may require significant auxiliary storage (depending on how
+ much temporary data needs to be stored). In general, if one iterator uses
+ most or all of the data before another iterator starts, it is faster to use
+ :func:`list` instead of :func:`tee`.
.. function:: zip_longest(*iterables, fillvalue=None)
- Make an iterator that aggregates elements from each of the iterables. If the
- iterables are of uneven length, missing values are filled-in with *fillvalue*.
- Iteration continues until the longest iterable is exhausted. Equivalent to::
-
- def zip_longest(*args, fillvalue=None):
- # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-
- def sentinel(counter = ([fillvalue]*(len(args)-1)).pop):
- yield counter() # yields the fillvalue, or raises IndexError
- fillers = repeat(fillvalue)
- iters = [chain(it, sentinel(), fillers) for it in args]
- try:
- for tup in zip(*iters):
- yield tup
- except IndexError:
- pass
-
- If one of the iterables is potentially infinite, then the :func:`zip_longest`
- function should be wrapped with something that limits the number of calls
- (for example :func:`islice` or :func:`takewhile`). If not specified,
- *fillvalue* defaults to ``None``.
+ Make an iterator that aggregates elements from each of the iterables. If the
+ iterables are of uneven length, missing values are filled-in with *fillvalue*.
+ Iteration continues until the longest iterable is exhausted. Equivalent to::
+
+ def zip_longest(*args, fillvalue=None):
+ # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-
+ def sentinel(counter = ([fillvalue]*(len(args)-1)).pop):
+ yield counter() # yields the fillvalue, or raises IndexError
+ fillers = repeat(fillvalue)
+ iters = [chain(it, sentinel(), fillers) for it in args]
+ try:
+ for tup in zip(*iters):
+ yield tup
+ except IndexError:
+ pass
+
+ If one of the iterables is potentially infinite, then the :func:`zip_longest`
+ function should be wrapped with something that limits the number of calls
+ (for example :func:`islice` or :func:`takewhile`). If not specified,
+ *fillvalue* defaults to ``None``.
.. _itertools-recipes:
@@ -576,176 +592,168 @@
.. testcode::
- def take(n, iterable):
- "Return first n items of the iterable as a list"
- return list(islice(iterable, n))
-
- def tabulate(function, start=0):
- "Return function(0), function(1), ..."
- return map(function, count(start))
-
- def consume(iterator, n):
- "Advance the iterator n-steps ahead. If n is none, consume entirely."
- # Use functions that consume iterators at C speed.
- if n is None:
- # feed the entire iterator into a zero-length deque
- collections.deque(iterator, maxlen=0)
- else:
- # advance to the empty slice starting at position n
- next(islice(iterator, n, n), None)
-
- def nth(iterable, n, default=None):
- "Returns the nth item or a default value"
- return next(islice(iterable, n, None), default)
-
- def quantify(iterable, pred=bool):
- "Count how many times the predicate is true"
- return sum(map(pred, iterable))
-
- def padnone(iterable):
- """Returns the sequence elements and then returns None indefinitely.
-
- Useful for emulating the behavior of the built-in map() function.
- """
- return chain(iterable, repeat(None))
-
- def ncycles(iterable, n):
- "Returns the sequence elements n times"
- return chain.from_iterable(repeat(tuple(iterable), n))
-
- def dotproduct(vec1, vec2):
- return sum(map(operator.mul, vec1, vec2))
-
- def flatten(listOfLists):
- "Flatten one level of nesting"
- return chain.from_iterable(listOfLists)
-
- def repeatfunc(func, times=None, *args):
- """Repeat calls to func with specified arguments.
-
- Example: repeatfunc(random.random)
- """
- if times is None:
- return starmap(func, repeat(args))
- return starmap(func, repeat(args, times))
-
- def pairwise(iterable):
- "s -> (s0,s1), (s1,s2), (s2, s3), ..."
- a, b = tee(iterable)
- next(b, None)
- return zip(a, b)
-
- def grouper(n, iterable, fillvalue=None):
- "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx"
- args = [iter(iterable)] * n
- return zip_longest(*args, fillvalue=fillvalue)
-
- def roundrobin(*iterables):
- "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
- # Recipe credited to George Sakkis
- pending = len(iterables)
- nexts = cycle(iter(it).__next__ for it in iterables)
- while pending:
- try:
- for next in nexts:
- yield next()
- except StopIteration:
- pending -= 1
- nexts = cycle(islice(nexts, pending))
-
- def accumulate(iterable):
- 'Emit a running total'
- # accumulate([1,2,3,4,5]) --> 1 3 6 10 15
- total = 0
- for element in iterable:
- total += element
- yield total
-
- def partition(pred, iterable):
- 'Use a predicate to partition entries into false entries and true entries'
- # partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9
- t1, t2 = tee(iterable)
- return filterfalse(pred, t1), filter(pred, t2)
-
- def powerset(iterable):
- "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
- s = list(iterable)
- return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
-
- def unique_everseen(iterable, key=None):
- "List unique elements, preserving order. Remember all elements ever seen."
- # unique_everseen('AAAABBBCCDAABBB') --> A B C D
- # unique_everseen('ABBCcAD', str.lower) --> A B C D
- seen = set()
- seen_add = seen.add
- if key is None:
- for element in filterfalse(seen.__contains__, iterable):
- seen_add(element)
- yield element
- else:
- for element in iterable:
- k = key(element)
- if k not in seen:
- seen_add(k)
- yield element
-
- def unique_justseen(iterable, key=None):
- "List unique elements, preserving order. Remember only the element just seen."
- # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
- # unique_justseen('ABBCcAD', str.lower) --> A B C A D
- return map(next, map(itemgetter(1), groupby(iterable, key)))
-
- def iter_except(func, exception, first=None):
- """ Call a function repeatedly until an exception is raised.
-
- Converts a call-until-exception interface to an iterator interface.
- Like __builtin__.iter(func, sentinel) but uses an exception instead
- of a sentinel to end the loop.
-
- Examples:
- iter_except(functools.partial(heappop, h), IndexError) # priority queue iterator
- iter_except(d.popitem, KeyError) # non-blocking dict iterator
- iter_except(d.popleft, IndexError) # non-blocking deque iterator
- iter_except(q.get_nowait, Queue.Empty) # loop over a producer Queue
- iter_except(s.pop, KeyError) # non-blocking set iterator
-
- """
- try:
- if first is not None:
- yield first() # For database APIs needing an initial cast to db.first()
- while 1:
- yield func()
- except exception:
- pass
-
- def random_product(*args, repeat=1):
- "Random selection from itertools.product(*args, **kwds)"
- pools = [tuple(pool) for pool in args] * repeat
- return tuple(random.choice(pool) for pool in pools)
-
- def random_permutation(iterable, r=None):
- "Random selection from itertools.permutations(iterable, r)"
- pool = tuple(iterable)
- r = len(pool) if r is None else r
- return tuple(random.sample(pool, r))
-
- def random_combination(iterable, r):
- "Random selection from itertools.combinations(iterable, r)"
- pool = tuple(iterable)
- n = len(pool)
- indices = sorted(random.sample(range(n), r))
- return tuple(pool[i] for i in indices)
-
- def random_combination_with_replacement(iterable, r):
- "Random selection from itertools.combinations_with_replacement(iterable, r)"
- pool = tuple(iterable)
- n = len(pool)
- indices = sorted(random.randrange(n) for i in range(r))
- return tuple(pool[i] for i in indices)
+ def take(n, iterable):
+ "Return first n items of the iterable as a list"
+ return list(islice(iterable, n))
+
+ def tabulate(function, start=0):
+ "Return function(0), function(1), ..."
+ return map(function, count(start))
+
+ def consume(iterator, n):
+ "Advance the iterator n-steps ahead. If n is none, consume entirely."
+ # Use functions that consume iterators at C speed.
+ if n is None:
+ # feed the entire iterator into a zero-length deque
+ collections.deque(iterator, maxlen=0)
+ else:
+ # advance to the empty slice starting at position n
+ next(islice(iterator, n, n), None)
+
+ def nth(iterable, n, default=None):
+ "Returns the nth item or a default value"
+ return next(islice(iterable, n, None), default)
+
+ def quantify(iterable, pred=bool):
+ "Count how many times the predicate is true"
+ return sum(map(pred, iterable))
+
+ def padnone(iterable):
+ """Returns the sequence elements and then returns None indefinitely.
+
+ Useful for emulating the behavior of the built-in map() function.
+ """
+ return chain(iterable, repeat(None))
+
+ def ncycles(iterable, n):
+ "Returns the sequence elements n times"
+ return chain.from_iterable(repeat(tuple(iterable), n))
+
+ def dotproduct(vec1, vec2):
+ return sum(map(operator.mul, vec1, vec2))
+
+ def flatten(listOfLists):
+ "Flatten one level of nesting"
+ return chain.from_iterable(listOfLists)
+
+ def repeatfunc(func, times=None, *args):
+ """Repeat calls to func with specified arguments.
+
+ Example: repeatfunc(random.random)
+ """
+ if times is None:
+ return starmap(func, repeat(args))
+ return starmap(func, repeat(args, times))
+
+ def pairwise(iterable):
+ "s -> (s0,s1), (s1,s2), (s2, s3), ..."
+ a, b = tee(iterable)
+ next(b, None)
+ return zip(a, b)
+
+ def grouper(n, iterable, fillvalue=None):
+ "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx"
+ args = [iter(iterable)] * n
+ return zip_longest(*args, fillvalue=fillvalue)
+
+ def roundrobin(*iterables):
+ "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
+ # Recipe credited to George Sakkis
+ pending = len(iterables)
+ nexts = cycle(iter(it).__next__ for it in iterables)
+ while pending:
+ try:
+ for next in nexts:
+ yield next()
+ except StopIteration:
+ pending -= 1
+ nexts = cycle(islice(nexts, pending))
+
+ def partition(pred, iterable):
+ 'Use a predicate to partition entries into false entries and true entries'
+ # partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9
+ t1, t2 = tee(iterable)
+ return filterfalse(pred, t1), filter(pred, t2)
+
+ def powerset(iterable):
+ "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
+ s = list(iterable)
+ return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
+
+ def unique_everseen(iterable, key=None):
+ "List unique elements, preserving order. Remember all elements ever seen."
+ # unique_everseen('AAAABBBCCDAABBB') --> A B C D
+ # unique_everseen('ABBCcAD', str.lower) --> A B C D
+ seen = set()
+ seen_add = seen.add
+ if key is None:
+ for element in filterfalse(seen.__contains__, iterable):
+ seen_add(element)
+ yield element
+ else:
+ for element in iterable:
+ k = key(element)
+ if k not in seen:
+ seen_add(k)
+ yield element
+
+ def unique_justseen(iterable, key=None):
+ "List unique elements, preserving order. Remember only the element just seen."
+ # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
+ # unique_justseen('ABBCcAD', str.lower) --> A B C A D
+ return map(next, map(itemgetter(1), groupby(iterable, key)))
+
+ def iter_except(func, exception, first=None):
+ """ Call a function repeatedly until an exception is raised.
+
+ Converts a call-until-exception interface to an iterator interface.
+ Like __builtin__.iter(func, sentinel) but uses an exception instead
+ of a sentinel to end the loop.
+
+ Examples:
+ iter_except(functools.partial(heappop, h), IndexError) # priority queue iterator
+ iter_except(d.popitem, KeyError) # non-blocking dict iterator
+ iter_except(d.popleft, IndexError) # non-blocking deque iterator
+ iter_except(q.get_nowait, Queue.Empty) # loop over a producer Queue
+ iter_except(s.pop, KeyError) # non-blocking set iterator
+
+ """
+ try:
+ if first is not None:
+ yield first() # For database APIs needing an initial cast to db.first()
+ while 1:
+ yield func()
+ except exception:
+ pass
+
+ def random_product(*args, repeat=1):
+ "Random selection from itertools.product(*args, **kwds)"
+ pools = [tuple(pool) for pool in args] * repeat
+ return tuple(random.choice(pool) for pool in pools)
+
+ def random_permutation(iterable, r=None):
+ "Random selection from itertools.permutations(iterable, r)"
+ pool = tuple(iterable)
+ r = len(pool) if r is None else r
+ return tuple(random.sample(pool, r))
+
+ def random_combination(iterable, r):
+ "Random selection from itertools.combinations(iterable, r)"
+ pool = tuple(iterable)
+ n = len(pool)
+ indices = sorted(random.sample(range(n), r))
+ return tuple(pool[i] for i in indices)
+
+ def random_combination_with_replacement(iterable, r):
+ "Random selection from itertools.combinations_with_replacement(iterable, r)"
+ pool = tuple(iterable)
+ n = len(pool)
+ indices = sorted(random.randrange(n) for i in range(r))
+ return tuple(pool[i] for i in indices)
Note, many of the above recipes can be optimized by replacing global lookups
with local variables defined as default values. For example, the
*dotproduct* recipe can be written as::
- def dotproduct(vec1, vec2, sum=sum, map=map, mul=operator.mul):
- return sum(map(mul, vec1, vec2))
+ def dotproduct(vec1, vec2, sum=sum, map=map, mul=operator.mul):
+ return sum(map(mul, vec1, vec2))
More information about the Python-checkins
mailing list