Doc/lib/libitertools.tex

   1 \section{\module{itertools} ---
   2          Functions creating iterators for efficient looping}
   3
   4 \declaremodule{standard}{itertools}
   5 \modulesynopsis{Functions creating iterators for efficient looping.}
   6 \moduleauthor{Raymond Hettinger}{python@rcn.com}
   7 \sectionauthor{Raymond Hettinger}{python@rcn.com}
   8 \versionadded{2.3}
   9
  10
  11 This module implements a number of iterator building blocks inspired
  12 by constructs from the Haskell and SML programming languages.  Each
  13 has been recast in a form suitable for Python.
  14
  15 The module standardizes a core set of fast, memory efficient tools
  16 that are useful by themselves or in combination.  Standardization helps
  17 avoid the readability and reliability problems which arise when many
  18 different individuals create their own slightly varying implementations,
  19 each with their own quirks and naming conventions.
  20
  21 The tools are designed to combine readily with one another.  This makes
  22 it easy to construct more specialized tools succinctly and efficiently
  23 in pure Python.
  24
  25 For instance, SML provides a tabulation tool: \code{tabulate(f)}
  26 which produces a sequence \code{f(0), f(1), ...}.  This toolbox
  27 provides \function{imap()} and \function{count()} which can be combined
  28 to form \code{imap(f, count())} and produce an equivalent result.
  29
  30 Likewise, the functional tools are designed to work well with the
  31 high-speed functions provided by the \refmodule{operator} module.
  32
  33 The module author welcomes suggestions for other basic building blocks
  34 to be added to future versions of the module.
  35
  36 Whether cast in pure python form or C code, tools that use iterators
  37 are more memory efficient (and faster) than their list based counterparts.
  38 Adopting the principles of just-in-time manufacturing, they create
  39 data when and where needed instead of consuming memory with the
  40 computer equivalent of ``inventory''.
  41
  42 The performance advantage of iterators becomes more acute as the number
  43 of elements increases -- at some point, lists grow large enough to
  44 severely impact memory cache performance and start running slowly.
  45
  46 \begin{seealso}
  47   \seetext{The Standard ML Basis Library,
  48            \citetitle[http://www.standardml.org/Basis/]
  49            {The Standard ML Basis Library}.}
  50
  51   \seetext{Haskell, A Purely Functional Language,
  52            \citetitle[http://www.haskell.org/definition/]
  53            {Definition of Haskell and the Standard Libraries}.}
  54 \end{seealso}
  55
  56
  57 \subsection{Itertool functions \label{itertools-functions}}
  58
  59 The following module functions all construct and return iterators.
  60 Some provide streams of infinite length, so they should only be accessed
  61 by functions or loops that truncate the stream.
  62
  63 \begin{funcdesc}{chain}{*iterables}
  64   Make an iterator that returns elements from the first iterable until
  65   it is exhausted, then proceeds to the next iterable, until all of the
  66   iterables are exhausted.  Used for treating consecutive sequences as
  67   a single sequence.  Equivalent to:
  68
  69   \begin{verbatim}
  70      def chain(*iterables):
  71          for it in iterables:
  72              for element in it:
  73                  yield element
  74   \end{verbatim}
  75 \end{funcdesc}
  76
  77 \begin{funcdesc}{count}{\optional{n}}
  78   Make an iterator that returns consecutive integers starting with \var{n}.
  79   If not specified \var{n} defaults to zero.
  80   Does not currently support python long integers.  Often used as an
  81   argument to \function{imap()} to generate consecutive data points.
  82   Also, used with \function{izip()} to add sequence numbers.  Equivalent to:
  83
  84   \begin{verbatim}
  85      def count(n=0):
  86          while True:
  87              yield n
  88              n += 1
  89   \end{verbatim}
  90
  91   Note, \function{count()} does not check for overflow and will return
  92   negative numbers after exceeding \code{sys.maxint}.  This behavior
  93   may change in the future.
  94 \end{funcdesc}
  95
  96 \begin{funcdesc}{cycle}{iterable}
  97   Make an iterator returning elements from the iterable and saving a
  98   copy of each.  When the iterable is exhausted, return elements from
  99   the saved copy.  Repeats indefinitely.  Equivalent to:
 100
 101   \begin{verbatim}
 102      def cycle(iterable):
 103          saved = []
 104          for element in iterable:
 105              yield element
 106              saved.append(element)
 107          while saved:
 108              for element in saved:
 109                    yield element
 110   \end{verbatim}
 111
 112   Note, this is the only member of the toolkit that may require
 113   significant auxiliary storage (depending on the length of the
 114   iterable).
 115 \end{funcdesc}
 116
 117 \begin{funcdesc}{dropwhile}{predicate, iterable}
 118   Make an iterator that drops elements from the iterable as long as
 119   the predicate is true; afterwards, returns every element.  Note,
 120   the iterator does not produce \emph{any} output until the predicate
 121   is true, so it may have a lengthy start-up time.  Equivalent to:
 122
 123   \begin{verbatim}
 124      def dropwhile(predicate, iterable):
 125          iterable = iter(iterable)
 126          for x in iterable:
 127              if not predicate(x):
 128                  yield x
 129                  break
 130          for x in iterable:
 131              yield x
 132   \end{verbatim}
 133 \end{funcdesc}
 134
 135 \begin{funcdesc}{ifilter}{predicate, iterable}
 136   Make an iterator that filters elements from iterable returning only
 137   those for which the predicate is \code{True}.
 138   If \var{predicate} is \code{None}, return the items that are true.
 139   Equivalent to:
 140
 141   \begin{verbatim}
 142      def ifilter(predicate, iterable):
 143          if predicate is None:
 144              predicate = bool
 145          for x in iterable:
 146              if predicate(x):
 147                  yield x
 148   \end{verbatim}
 149 \end{funcdesc}
 150
 151 \begin{funcdesc}{ifilterfalse}{predicate, iterable}
 152   Make an iterator that filters elements from iterable returning only
 153   those for which the predicate is \code{False}.
 154   If \var{predicate} is \code{None}, return the items that are false.
 155   Equivalent to:
 156
 157   \begin{verbatim}
 158      def ifilterfalse(predicate, iterable):
 159          if predicate is None:
 160              predicate = bool
 161          for x in iterable:
 162              if not predicate(x):
 163                  yield x
 164   \end{verbatim}
 165 \end{funcdesc}
 166
 167 \begin{funcdesc}{imap}{function, *iterables}
 168   Make an iterator that computes the function using arguments from
 169   each of the iterables.  If \var{function} is set to \code{None}, then
 170   \function{imap()} returns the arguments as a tuple.  Like
 171   \function{map()} but stops when the shortest iterable is exhausted
 172   instead of filling in \code{None} for shorter iterables.  The reason
 173   for the difference is that infinite iterator arguments are typically
 174   an error for \function{map()} (because the output is fully evaluated)
 175   but represent a common and useful way of supplying arguments to
 176   \function{imap()}.
 177   Equivalent to:
 178
 179   \begin{verbatim}
 180      def imap(function, *iterables):
 181          iterables = map(iter, iterables)
 182          while True:
 183              args = [i.next() for i in iterables]
 184              if function is None:
 185                  yield tuple(args)
 186              else:
 187                  yield function(*args)
 188   \end{verbatim}
 189 \end{funcdesc}
 190
 191 \begin{funcdesc}{islice}{iterable, \optional{start,} stop \optional{, step}}
 192   Make an iterator that returns selected elements from the iterable.
 193   If \var{start} is non-zero, then elements from the iterable are skipped
 194   until start is reached.  Afterward, elements are returned consecutively
 195   unless \var{step} is set higher than one which results in items being
 196   skipped.  If \var{stop} is \code{None}, then iteration continues until
 197   the iterator is exhausted, if at all; otherwise, it stops at the specified
 198   position.  Unlike regular slicing,
 199   \function{islice()} does not support negative values for \var{start},
 200   \var{stop}, or \var{step}.  Can be used to extract related fields
 201   from data where the internal structure has been flattened (for
 202   example, a multi-line report may list a name field on every
 203   third line).  Equivalent to:
 204
 205   \begin{verbatim}
 206      def islice(iterable, *args):
 207          s = slice(*args)
 208          next, stop, step = s.start or 0, s.stop, s.step or 1
 209          for cnt, element in enumerate(iterable):
 210              if cnt < next:
 211                  continue
 212              if stop is not None and cnt >= stop:
 213                  break
 214              yield element
 215              next += step
 216   \end{verbatim}
 217 \end{funcdesc}
 218
 219 \begin{funcdesc}{izip}{*iterables}
 220   Make an iterator that aggregates elements from each of the iterables.
 221   Like \function{zip()} except that it returns an iterator instead of
 222   a list.  Used for lock-step iteration over several iterables at a
 223   time.  Equivalent to:
 224
 225   \begin{verbatim}
 226      def izip(*iterables):
 227          iterables = map(iter, iterables)
 228          while iterables:
 229              result = [i.next() for i in iterables]
 230              yield tuple(result)
 231   \end{verbatim}
 232
 233   \versionchanged[When no iterables are specified, returns a zero length
 234                   iterator instead of raising a TypeError exception]{2.3.1}
 235 \end{funcdesc}
 236
 237 \begin{funcdesc}{repeat}{object\optional{, times}}
 238   Make an iterator that returns \var{object} over and over again.
 239   Runs indefinitely unless the \var{times} argument is specified.
 240   Used as argument to \function{imap()} for invariant parameters
 241   to the called function.  Also used with \function{izip()} to create
 242   an invariant part of a tuple record.  Equivalent to:
 243
 244   \begin{verbatim}
 245      def repeat(object, times=None):
 246          if times is None:
 247              while True:
 248                  yield object
 249          else:
 250              for i in xrange(times):
 251                  yield object
 252   \end{verbatim}
 253 \end{funcdesc}
 254
 255 \begin{funcdesc}{starmap}{function, iterable}
 256   Make an iterator that computes the function using arguments tuples
 257   obtained from the iterable.  Used instead of \function{imap()} when
 258   argument parameters are already grouped in tuples from a single iterable
 259   (the data has been ``pre-zipped'').  The difference between
 260   \function{imap()} and \function{starmap()} parallels the distinction
 261   between \code{function(a,b)} and \code{function(*c)}.
 262   Equivalent to:
 263
 264   \begin{verbatim}
 265      def starmap(function, iterable):
 266          iterable = iter(iterable)
 267          while True:
 268              yield function(*iterable.next())
 269   \end{verbatim}
 270 \end{funcdesc}
 271
 272 \begin{funcdesc}{takewhile}{predicate, iterable}
 273   Make an iterator that returns elements from the iterable as long as
 274   the predicate is true.  Equivalent to:
 275
 276   \begin{verbatim}
 277      def takewhile(predicate, iterable):
 278          for x in iterable:
 279              if predicate(x):
 280                  yield x
 281              else:
 282                  break
 283   \end{verbatim}
 284 \end{funcdesc}
 285
 286
 287 \subsection{Examples \label{itertools-example}}
 288
 289 The following examples show common uses for each tool and
 290 demonstrate ways they can be combined.
 291
 292 \begin{verbatim}
 293
 294 >>> amounts = [120.15, 764.05, 823.14]
 295 >>> for checknum, amount in izip(count(1200), amounts):
 296 ...     print 'Check %d is for $%.2f' % (checknum, amount)
 297 ...
 298 Check 1200 is for $120.15
 299 Check 1201 is for $764.05
 300 Check 1202 is for $823.14
 301
 302 >>> import operator
 303 >>> for cube in imap(operator.pow, xrange(1,4), repeat(3)):
 304 ...    print cube
 305 ...
 306 1
 307 8
 308 27
 309
 310 >>> reportlines = ['EuroPython', 'Roster', '', 'alex', '', 'laura',
 311                   '', 'martin', '', 'walter', '', 'samuele']
 312 >>> for name in islice(reportlines, 3, None, 2):
 313 ...    print name.title()
 314 ...
 315 Alex
 316 Laura
 317 Martin
 318 Walter
 319 Samuele
 320
 321 \end{verbatim}
 322
 323 This section shows how itertools can be combined to create other more
 324 powerful itertools.  Note that \function{enumerate()} and \method{iteritems()}
 325 already have efficient implementations in Python.  They are only included here
 326 to illustrate how higher level tools can be created from building blocks.
 327
 328 \begin{verbatim}
 329 def take(n, seq):
 330     return list(islice(seq, n))
 331
 332 def enumerate(iterable):
 333     return izip(count(), iterable)
 334
 335 def tabulate(function):
 336     "Return function(0), function(1), ..."
 337     return imap(function, count())
 338
 339 def iteritems(mapping):
 340     return izip(mapping.iterkeys(), mapping.itervalues())
 341
 342 def nth(iterable, n):
 343     "Returns the nth item"
 344     return list(islice(iterable, n, n+1))
 345
 346 def all(seq, pred=bool):
 347     "Returns True if pred(x) is True for every element in the iterable"
 348     return False not in imap(pred, seq)
 349
 350 def any(seq, pred=bool):
 351     "Returns True if pred(x) is True at least one element in the iterable"
 352     return True in imap(pred, seq)
 353
 354 def no(seq, pred=bool):
 355     "Returns True if pred(x) is False for every element in the iterable"
 356     return True not in imap(pred, seq)
 357
 358 def quantify(seq, pred=bool):
 359     "Count how many times the predicate is True in the sequence"
 360     return sum(imap(pred, seq))
 361
 362 def padnone(seq):
 363     "Returns the sequence elements and then returns None indefinitely"
 364     return chain(seq, repeat(None))
 365
 366 def ncycles(seq, n):
 367     "Returns the sequence elements n times"
 368     return chain(*repeat(seq, n))
 369
 370 def dotproduct(vec1, vec2):
 371     return sum(imap(operator.mul, vec1, vec2))
 372
 373 def window(seq, n=2):
 374     "Returns a sliding window (of width n) over data from the iterable"
 375     "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
 376     it = iter(seq)
 377     result = tuple(islice(it, n))
 378     if len(result) == n:
 379         yield result
 380     for elem in it:
 381         result = result[1:] + (elem,)
 382         yield result
 383
 384 def tee(iterable):
 385     "Return two independent iterators from a single iterable"
 386     def gen(next, data={}, cnt=[0]):
 387         dpop = data.pop
 388         for i in count():
 389             if i == cnt[0]:
 390                 item = data[i] = next()
 391                 cnt[0] += 1
 392             else:
 393                 item = dpop(i)
 394             yield item
 395     next = iter(iterable).next
 396     return (gen(next), gen(next))
 397
 398 \end{verbatim}