libitertools.tex 17.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14
\section{\module{itertools} ---
         Functions creating iterators for efficient looping}

\declaremodule{standard}{itertools}
\modulesynopsis{Functions creating iterators for efficient looping.}
\moduleauthor{Raymond Hettinger}{python@rcn.com}
\sectionauthor{Raymond Hettinger}{python@rcn.com}
\versionadded{2.3}


This module implements a number of iterator building blocks inspired
by constructs from the Haskell and SML programming languages.  Each
has been recast in a form suitable for Python.

Raymond Hettinger's avatar
Raymond Hettinger committed
15 16 17 18 19 20
The module standardizes a core set of fast, memory efficient tools
that are useful by themselves or in combination.  Standardization helps
avoid the readability and reliability problems which arise when many
different individuals create their own slightly varying implementations,
each with their own quirks and naming conventions.

Raymond Hettinger's avatar
Raymond Hettinger committed
21
The tools are designed to combine readily with one another.  This makes
Raymond Hettinger's avatar
Raymond Hettinger committed
22 23 24
it easy to construct more specialized tools succinctly and efficiently
in pure Python.

Raymond Hettinger's avatar
Raymond Hettinger committed
25
For instance, SML provides a tabulation tool: \code{tabulate(f)}
Raymond Hettinger's avatar
Raymond Hettinger committed
26 27
which produces a sequence \code{f(0), f(1), ...}.  This toolbox
provides \function{imap()} and \function{count()} which can be combined
Raymond Hettinger's avatar
Raymond Hettinger committed
28
to form \code{imap(f, count())} and produce an equivalent result.
Raymond Hettinger's avatar
Raymond Hettinger committed
29

30 31 32 33 34 35
Likewise, the functional tools are designed to work well with the
high-speed functions provided by the \refmodule{operator} module.

The module author welcomes suggestions for other basic building blocks
to be added to future versions of the module.

36
Whether cast in pure python form or compiled code, tools that use iterators
Raymond Hettinger's avatar
Raymond Hettinger committed
37 38 39 40 41
are more memory efficient (and faster) than their list based counterparts.
Adopting the principles of just-in-time manufacturing, they create
data when and where needed instead of consuming memory with the
computer equivalent of ``inventory''.

42 43
The performance advantage of iterators becomes more acute as the number
of elements increases -- at some point, lists grow large enough to
44
severely impact memory cache performance and start running slowly.
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

\begin{seealso}
  \seetext{The Standard ML Basis Library,
           \citetitle[http://www.standardml.org/Basis/]
           {The Standard ML Basis Library}.}

  \seetext{Haskell, A Purely Functional Language,
           \citetitle[http://www.haskell.org/definition/]
           {Definition of Haskell and the Standard Libraries}.}
\end{seealso}


\subsection{Itertool functions \label{itertools-functions}}

The following module functions all construct and return iterators.
Some provide streams of infinite length, so they should only be accessed
by functions or loops that truncate the stream.

63 64 65 66 67 68 69 70 71 72 73 74 75 76
\begin{funcdesc}{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:

  \begin{verbatim}
     def chain(*iterables):
         for it in iterables:
             for element in it:
                 yield element
  \end{verbatim}
\end{funcdesc}

77 78
\begin{funcdesc}{count}{\optional{n}}
  Make an iterator that returns consecutive integers starting with \var{n}.
79
  If not specified \var{n} defaults to zero.  
80 81
  Does not currently support python long integers.  Often used as an
  argument to \function{imap()} to generate consecutive data points.
Raymond Hettinger's avatar
Raymond Hettinger committed
82
  Also, used with \function{izip()} to add sequence numbers.  Equivalent to:
83 84 85 86

  \begin{verbatim}
     def count(n=0):
         while True:
Raymond Hettinger's avatar
Raymond Hettinger committed
87 88
             yield n
             n += 1
89
  \end{verbatim}
90 91 92 93

  Note, \function{count()} does not check for overflow and will return
  negative numbers after exceeding \code{sys.maxint}.  This behavior
  may change in the future.
94 95
\end{funcdesc}

96 97 98 99 100 101 102 103 104 105 106
\begin{funcdesc}{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:

  \begin{verbatim}
     def cycle(iterable):
         saved = []
         for element in iterable:
             yield element
             saved.append(element)
Raymond Hettinger's avatar
Raymond Hettinger committed
107
         while saved:
108 109 110 111
             for element in saved:
                   yield element
  \end{verbatim}

112 113
  Note, this member of the toolkit may require significant
  auxiliary storage (depending on the length of the iterable).
114 115
\end{funcdesc}

116 117 118 119 120 121 122 123 124
\begin{funcdesc}{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 \emph{any} output until the predicate
  is true, so it may have a lengthy start-up time.  Equivalent to:

  \begin{verbatim}
     def dropwhile(predicate, iterable):
         iterable = iter(iterable)
Raymond Hettinger's avatar
Raymond Hettinger committed
125 126 127 128 129
         for x in iterable:
             if not predicate(x):
                 yield x
                 break
         for x in iterable:
130 131 132 133
             yield x
  \end{verbatim}
\end{funcdesc}

134 135
\begin{funcdesc}{groupby}{iterable\optional{, key}}
  Make an iterator that returns consecutive keys and groups from the
136
  \var{iterable}.  \var{key} is a function computing a key value for each
137
  element.  If not specified or is \code{None}, \var{key} defaults to an
138
  identity function and returns  the element unchanged.  Generally, the
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
  iterable needs to already be sorted on the same key function.

  The returned group is itself an iterator that shares the underlying
  iterable with \function{groupby()}.  Because the source is shared, when
  the \function{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:

  \begin{verbatim}
    groups = []
    uniquekeys = []
    for k, g in groupby(data, keyfunc):
        groups.append(list(g))      # Store group iterator as a list
        uniquekeys.append(k)
  \end{verbatim}

  \function{groupby()} is equivalent to:

  \begin{verbatim}
    class groupby(object):
        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 = xrange(0)
        def __iter__(self):
            return self
        def next(self):
            while self.currkey == self.tgtkey:
                self.currvalue = self.it.next() # 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 = self.it.next() # Exit on StopIteration
                self.currkey = self.keyfunc(self.currvalue)
  \end{verbatim}
  \versionadded{2.4}
\end{funcdesc}

Raymond Hettinger's avatar
Raymond Hettinger committed
182
\begin{funcdesc}{ifilter}{predicate, iterable}
183
  Make an iterator that filters elements from iterable returning only
Raymond Hettinger's avatar
Raymond Hettinger committed
184 185 186
  those for which the predicate is \code{True}.
  If \var{predicate} is \code{None}, return the items that are true.
  Equivalent to:
187 188

  \begin{verbatim}
Raymond Hettinger's avatar
Raymond Hettinger committed
189 190
     def ifilter(predicate, iterable):
         if predicate is None:
191
             predicate = bool
Raymond Hettinger's avatar
Raymond Hettinger committed
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
         for x in iterable:
             if predicate(x):
                 yield x
  \end{verbatim}
\end{funcdesc}

\begin{funcdesc}{ifilterfalse}{predicate, iterable}
  Make an iterator that filters elements from iterable returning only
  those for which the predicate is \code{False}.
  If \var{predicate} is \code{None}, return the items that are false.
  Equivalent to:

  \begin{verbatim}
     def ifilterfalse(predicate, iterable):
         if predicate is None:
207
             predicate = bool
Raymond Hettinger's avatar
Raymond Hettinger committed
208 209
         for x in iterable:
             if not predicate(x):
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242
                 yield x
  \end{verbatim}
\end{funcdesc}

\begin{funcdesc}{imap}{function, *iterables}
  Make an iterator that computes the function using arguments from
  each of the iterables.  If \var{function} is set to \code{None}, then
  \function{imap()} returns the arguments as a tuple.  Like
  \function{map()} but stops when the shortest iterable is exhausted
  instead of filling in \code{None} for shorter iterables.  The reason
  for the difference is that infinite iterator arguments are typically
  an error for \function{map()} (because the output is fully evaluated)
  but represent a common and useful way of supplying arguments to
  \function{imap()}.
  Equivalent to:

  \begin{verbatim}
     def imap(function, *iterables):
         iterables = map(iter, iterables)
         while True:
             args = [i.next() for i in iterables]
             if function is None:
                 yield tuple(args)
             else:
                 yield function(*args)
  \end{verbatim}
\end{funcdesc}

\begin{funcdesc}{islice}{iterable, \optional{start,} stop \optional{, step}}
  Make an iterator that returns selected elements from the iterable.
  If \var{start} is non-zero, then elements from the iterable are skipped
  until start is reached.  Afterward, elements are returned consecutively
  unless \var{step} is set higher than one which results in items being
243 244 245
  skipped.  If \var{stop} is \code{None}, then iteration continues until
  the iterator is exhausted, if at all; otherwise, it stops at the specified
  position.  Unlike regular slicing,
246 247 248 249 250 251 252 253
  \function{islice()} does not support negative values for \var{start},
  \var{stop}, or \var{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:

  \begin{verbatim}
     def islice(iterable, *args):
254
         s = slice(*args)
Raymond Hettinger's avatar
Raymond Hettinger committed
255
         next, stop, step = s.start or 0, s.stop, s.step or 1
Raymond Hettinger's avatar
Raymond Hettinger committed
256 257 258
         for cnt, element in enumerate(iterable):
             if cnt < next:
                 continue
259
             if stop is not None and cnt >= stop:
Raymond Hettinger's avatar
Raymond Hettinger committed
260 261
                 break
             yield element
262
             next += step             
263 264 265 266 267 268 269 270 271 272 273 274
  \end{verbatim}
\end{funcdesc}

\begin{funcdesc}{izip}{*iterables}
  Make an iterator that aggregates elements from each of the iterables.
  Like \function{zip()} except that it returns an iterator instead of
  a list.  Used for lock-step iteration over several iterables at a
  time.  Equivalent to:

  \begin{verbatim}
     def izip(*iterables):
         iterables = map(iter, iterables)
275
         while iterables:
276 277 278
             result = [i.next() for i in iterables]
             yield tuple(result)
  \end{verbatim}
279 280 281

  \versionchanged[When no iterables are specified, returns a zero length
                  iterator instead of raising a TypeError exception]{2.4}  
282 283
\end{funcdesc}

284
\begin{funcdesc}{repeat}{object\optional{, times}}
Raymond Hettinger's avatar
Raymond Hettinger committed
285
  Make an iterator that returns \var{object} over and over again.
286
  Runs indefinitely unless the \var{times} argument is specified.
287
  Used as argument to \function{imap()} for invariant parameters
Raymond Hettinger's avatar
Raymond Hettinger committed
288
  to the called function.  Also used with \function{izip()} to create
289 290 291
  an invariant part of a tuple record.  Equivalent to:

  \begin{verbatim}
292 293 294 295 296 297 298
     def repeat(object, times=None):
         if times is None:
             while True:
                 yield object
         else:
             for i in xrange(times):
                 yield object
299 300 301 302 303 304 305 306
  \end{verbatim}
\end{funcdesc}

\begin{funcdesc}{starmap}{function, iterable}
  Make an iterator that computes the function using arguments tuples
  obtained from the iterable.  Used instead of \function{imap()} when
  argument parameters are already grouped in tuples from a single iterable
  (the data has been ``pre-zipped'').  The difference between
Raymond Hettinger's avatar
Raymond Hettinger committed
307
  \function{imap()} and \function{starmap()} parallels the distinction
308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324
  between \code{function(a,b)} and \code{function(*c)}.
  Equivalent to:

  \begin{verbatim}
     def starmap(function, iterable):
         iterable = iter(iterable)
         while True:
             yield function(*iterable.next())
  \end{verbatim}
\end{funcdesc}

\begin{funcdesc}{takewhile}{predicate, iterable}
  Make an iterator that returns elements from the iterable as long as
  the predicate is true.  Equivalent to:

  \begin{verbatim}
     def takewhile(predicate, iterable):
Raymond Hettinger's avatar
Raymond Hettinger committed
325
         for x in iterable:
326 327 328 329 330 331 332
             if predicate(x):
                 yield x
             else:
                 break
  \end{verbatim}
\end{funcdesc}

333 334 335
\begin{funcdesc}{tee}{iterable\optional{, n=2}}
  Return \var{n} independent iterators from a single iterable.
  The case where \var{n} is two is equivalent to:
336 337 338 339 340 341 342 343 344 345 346 347 348 349 350

  \begin{verbatim}
     def tee(iterable):
         def gen(next, data={}, cnt=[0]):
             for i in count():
                 if i == cnt[0]:
                     item = data[i] = next()
                     cnt[0] += 1
                 else:
                     item = data.pop(i)
                 yield item
         it = iter(iterable)
         return (gen(it.next), gen(it.next))
  \end{verbatim}

351 352 353 354
  Note, once \function{tee()} has made a split, the original \var{iterable}
  should not be used anywhere else; otherwise, the \var{iterable} could get
  advanced without the tee objects being informed.

355 356
  Note, this member of the toolkit may require significant auxiliary
  storage (depending on how much temporary data needs to be stored).
Andrew M. Kuchling's avatar
Andrew M. Kuchling committed
357
  In general, if one iterator is going to use most or all of the data before
358 359 360 361 362
  the other iterator, it is faster to use \function{list()} instead of
  \function{tee()}.
  \versionadded{2.4}
\end{funcdesc}

363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379

\subsection{Examples \label{itertools-example}}

The following examples show common uses for each tool and
demonstrate ways they can be combined.

\begin{verbatim}

>>> amounts = [120.15, 764.05, 823.14]
>>> for checknum, amount in izip(count(1200), amounts):
...     print 'Check %d is for $%.2f' % (checknum, amount)
...
Check 1200 is for $120.15
Check 1201 is for $764.05
Check 1202 is for $823.14

>>> import operator
380
>>> for cube in imap(operator.pow, xrange(1,5), repeat(3)):
381 382 383 384 385
...    print cube
...
1
8
27
386
64
387 388

>>> reportlines = ['EuroPython', 'Roster', '', 'alex', '', 'laura',
389
                  '', 'martin', '', 'walter', '', 'mark']
390
>>> for name in islice(reportlines, 3, None, 2):
391 392 393 394 395 396
...    print name.title()
...
Alex
Laura
Martin
Walter
397
Mark
398

399 400 401
# Show a dictionary sorted and grouped by value
>>> from operator import itemgetter
>>> d = dict(a=1, b=2, c=1, d=2, e=1, f=2, g=3)
402
>>> di = sorted(d.iteritems(), key=itemgetter(1))
403 404 405 406 407 408 409
>>> for k, g in groupby(di, key=itemgetter(1)):
...     print k, map(itemgetter(0), g)
...
1 ['a', 'c', 'e']
2 ['b', 'd', 'f']
3 ['g']

410 411 412 413 414 415 416 417 418 419 420 421 422
# Find runs of consecutive numbers using groupby.  The key to the solution
# is differencing with a range so that consecutive numbers all appear in
# same group.
>>> data = [ 1,  4,5,6, 10, 15,16,17,18, 22, 25,26,27,28]
>>> for k, g in groupby(enumerate(data), lambda (i,x):i-x):
...     print map(operator.itemgetter(1), g)
... 
[1]
[4, 5, 6]
[10]
[15, 16, 17, 18]
[22]
[25, 26, 27, 28]
423

424 425
\end{verbatim}

426 427 428 429 430 431 432 433 434 435 436 437 438 439

\subsection{Recipes \label{itertools-recipes}}

This section shows recipes for creating an extended toolset using the
existing itertools as building blocks.

The extended tools offer the same high performance as the underlying
toolset.  The superior memory performance is kept by processing elements one
at a time rather than bringing the whole iterable into memory all at once.
Code volume is kept small by linking the tools together in a functional style
which helps eliminate temporary variables.  High speed is retained by
preferring ``vectorized'' building blocks over the use of for-loops and
generators which incur interpreter overhead.

440 441

\begin{verbatim}
442 443 444
def take(n, seq):
    return list(islice(seq, n))

445 446 447 448 449 450 451 452 453 454 455 456 457 458
def enumerate(iterable):
    return izip(count(), iterable)

def tabulate(function):
    "Return function(0), function(1), ..."
    return imap(function, count())

def iteritems(mapping):
    return izip(mapping.iterkeys(), mapping.itervalues())

def nth(iterable, n):
    "Returns the nth item"
    return list(islice(iterable, n, n+1))

459
def all(seq, pred=bool):
460 461 462
    "Returns True if pred(x) is True for every element in the iterable"
    return False not in imap(pred, seq)

463
def any(seq, pred=bool):
464 465 466
    "Returns True if pred(x) is True at least one element in the iterable"
    return True in imap(pred, seq)

467
def no(seq, pred=bool):
468 469 470
    "Returns True if pred(x) is False for every element in the iterable"
    return True not in imap(pred, seq)

471
def quantify(seq, pred=bool):
472 473 474 475
    "Count how many times the predicate is True in the sequence"
    return sum(imap(pred, seq))

def padnone(seq):
476 477 478 479 480
    """Returns the sequence elements and then returns None indefinitely.

    Useful for emulating the behavior of the built-in map() function.

    """
481 482 483 484 485 486 487 488 489
    return chain(seq, repeat(None))

def ncycles(seq, n):
    "Returns the sequence elements n times"
    return chain(*repeat(seq, n))

def dotproduct(vec1, vec2):
    return sum(imap(operator.mul, vec1, vec2))

490 491 492 493
def flatten(listOfLists):
    return list(chain(*listOfLists))

def repeatfunc(func, times=None, *args):
494 495 496 497 498
    """Repeat calls to func with specified arguments.
    
    Example:  repeatfunc(random.random)
    
    """
499 500 501 502 503
    if times is None:
        return starmap(func, repeat(args))
    else:
        return starmap(func, repeat(args, times))

504 505 506
def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
507 508 509 510 511
    try:
        b.next()
    except StopIteration:
        pass
    return izip(a, b)
512

513
\end{verbatim}