Raymond Hettinger | 96ef811 | 2003-02-01 00:10:11 +0000 | [diff] [blame^] | 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 | With the advent of iterators and generators in Python 2.3, each of |
| 16 | these tools can be expressed easily and succinctly in pure python. |
| 17 | Rather duplicating what can already be done, this module emphasizes |
| 18 | providing value in other ways: |
| 19 | |
| 20 | \begin{itemize} |
| 21 | |
| 22 | \item Instead of constructing an over-specialized toolset, this module |
| 23 | provides basic building blocks that can be readily combined. |
| 24 | |
| 25 | For instance, SML provides a tabulation tool: \code{tabulate(\var{f})} |
| 26 | which produces a sequence \code{f(0), f(1), ...}. This toolbox |
| 27 | takes a different approach of providing \function{imap()} and |
| 28 | \function{count()} which can be combined to form |
| 29 | \code{imap(\var{f}, count())} and produce an equivalent result. |
| 30 | |
| 31 | \item Some tools were dropped because they offer no advantage over their |
| 32 | pure python counterparts or because their behavior was too |
| 33 | surprising. |
| 34 | |
| 35 | For instance, SML provides a tool: \code{cycle(\var{seq})} which |
| 36 | loops over the sequence elements and then starts again when the |
| 37 | sequence is exhausted. The surprising behavior is the need for |
| 38 | significant auxiliary storage (unusual for iterators). Also, it |
| 39 | is trivially implemented in python with almost no performance |
| 40 | penalty. |
| 41 | |
| 42 | \item Another source of value comes from standardizing a core set of tools |
| 43 | to avoid the readability and reliability problems that arise when many |
| 44 | different individuals create their own slightly varying implementations |
| 45 | each with their own quirks and naming conventions. |
| 46 | |
| 47 | \item Whether cast in pure python form or C code, tools that use iterators |
| 48 | are more memory efficient (and faster) than their list based counterparts. |
| 49 | Adopting the principles of just-in-time manufacturing, they create |
| 50 | data when and where needed instead of consuming memory with the |
| 51 | computer equivalent of ``inventory''. |
| 52 | |
| 53 | \end{itemize} |
| 54 | |
| 55 | \begin{seealso} |
| 56 | \seetext{The Standard ML Basis Library, |
| 57 | \citetitle[http://www.standardml.org/Basis/] |
| 58 | {The Standard ML Basis Library}.} |
| 59 | |
| 60 | \seetext{Haskell, A Purely Functional Language, |
| 61 | \citetitle[http://www.haskell.org/definition/] |
| 62 | {Definition of Haskell and the Standard Libraries}.} |
| 63 | \end{seealso} |
| 64 | |
| 65 | |
| 66 | \subsection{Itertool functions \label{itertools-functions}} |
| 67 | |
| 68 | The following module functions all construct and return iterators. |
| 69 | Some provide streams of infinite length, so they should only be accessed |
| 70 | by functions or loops that truncate the stream. |
| 71 | |
| 72 | \begin{funcdesc}{count}{\optional{n}} |
| 73 | Make an iterator that returns consecutive integers starting with \var{n}. |
| 74 | Does not currently support python long integers. Often used as an |
| 75 | argument to \function{imap()} to generate consecutive data points. |
| 76 | Also, used in \function{izip()} to add sequence numbers. Equivalent to: |
| 77 | |
| 78 | \begin{verbatim} |
| 79 | def count(n=0): |
| 80 | cnt = n |
| 81 | while True: |
| 82 | yield cnt |
| 83 | cnt += 1 |
| 84 | \end{verbatim} |
| 85 | \end{funcdesc} |
| 86 | |
| 87 | \begin{funcdesc}{dropwhile}{predicate, iterable} |
| 88 | Make an iterator that drops elements from the iterable as long as |
| 89 | the predicate is true; afterwards, returns every element. Note, |
| 90 | the iterator does not produce \emph{any} output until the predicate |
| 91 | is true, so it may have a lengthy start-up time. Equivalent to: |
| 92 | |
| 93 | \begin{verbatim} |
| 94 | def dropwhile(predicate, iterable): |
| 95 | iterable = iter(iterable) |
| 96 | while True: |
| 97 | x = iterable.next() |
| 98 | if predicate(x): continue # drop when predicate is true |
| 99 | yield x |
| 100 | break |
| 101 | while True: |
| 102 | yield iterable.next() |
| 103 | \end{verbatim} |
| 104 | \end{funcdesc} |
| 105 | |
| 106 | \begin{funcdesc}{ifilter}{predicate, iterable \optional{, invert}} |
| 107 | Make an iterator that filters elements from iterable returning only |
| 108 | those for which the predicate is \code{True}. If |
| 109 | \var{invert} is \code{True}, then reverse the process and pass through |
| 110 | only those elements for which the predicate is \code{False}. |
| 111 | If \var{predicate} is \code{None}, return the items that are true |
| 112 | (or false if \var{invert} has been set). Equivalent to: |
| 113 | |
| 114 | \begin{verbatim} |
| 115 | def ifilter(predicate, iterable, invert=False): |
| 116 | iterable = iter(iterable) |
| 117 | while True: |
| 118 | x = iterable.next() |
| 119 | if predicate is None: |
| 120 | b = bool(x) |
| 121 | else: |
| 122 | b = bool(predicate(x)) |
| 123 | if not invert and b or invert and not b: |
| 124 | yield x |
| 125 | \end{verbatim} |
| 126 | \end{funcdesc} |
| 127 | |
| 128 | \begin{funcdesc}{imap}{function, *iterables} |
| 129 | Make an iterator that computes the function using arguments from |
| 130 | each of the iterables. If \var{function} is set to \code{None}, then |
| 131 | \function{imap()} returns the arguments as a tuple. Like |
| 132 | \function{map()} but stops when the shortest iterable is exhausted |
| 133 | instead of filling in \code{None} for shorter iterables. The reason |
| 134 | for the difference is that infinite iterator arguments are typically |
| 135 | an error for \function{map()} (because the output is fully evaluated) |
| 136 | but represent a common and useful way of supplying arguments to |
| 137 | \function{imap()}. |
| 138 | Equivalent to: |
| 139 | |
| 140 | \begin{verbatim} |
| 141 | def imap(function, *iterables): |
| 142 | iterables = map(iter, iterables) |
| 143 | while True: |
| 144 | args = [i.next() for i in iterables] |
| 145 | if function is None: |
| 146 | yield tuple(args) |
| 147 | else: |
| 148 | yield function(*args) |
| 149 | \end{verbatim} |
| 150 | \end{funcdesc} |
| 151 | |
| 152 | \begin{funcdesc}{islice}{iterable, \optional{start,} stop \optional{, step}} |
| 153 | Make an iterator that returns selected elements from the iterable. |
| 154 | If \var{start} is non-zero, then elements from the iterable are skipped |
| 155 | until start is reached. Afterward, elements are returned consecutively |
| 156 | unless \var{step} is set higher than one which results in items being |
| 157 | skipped. If \var{stop} is specified, then iteration stops at the |
| 158 | specified element position; otherwise, it continues indefinitely or |
| 159 | until the iterable is exhausted. Unlike regular slicing, |
| 160 | \function{islice()} does not support negative values for \var{start}, |
| 161 | \var{stop}, or \var{step}. Can be used to extract related fields |
| 162 | from data where the internal structure has been flattened (for |
| 163 | example, a multi-line report may list a name field on every |
| 164 | third line). Equivalent to: |
| 165 | |
| 166 | \begin{verbatim} |
| 167 | def islice(iterable, *args): |
| 168 | iterable = iter(iterable) |
| 169 | s = slice(*args) |
| 170 | next = s.start or 0 |
| 171 | stop = s.stop |
| 172 | step = s.step or 1 |
| 173 | cnt = 0 |
| 174 | while True: |
| 175 | while cnt < next: |
| 176 | dummy = iterable.next() |
| 177 | cnt += 1 |
| 178 | if cnt >= stop: |
| 179 | break |
| 180 | yield iterable.next() |
| 181 | cnt += 1 |
| 182 | next += step |
| 183 | \end{verbatim} |
| 184 | \end{funcdesc} |
| 185 | |
| 186 | \begin{funcdesc}{izip}{*iterables} |
| 187 | Make an iterator that aggregates elements from each of the iterables. |
| 188 | Like \function{zip()} except that it returns an iterator instead of |
| 189 | a list. Used for lock-step iteration over several iterables at a |
| 190 | time. Equivalent to: |
| 191 | |
| 192 | \begin{verbatim} |
| 193 | def izip(*iterables): |
| 194 | iterables = map(iter, iterables) |
| 195 | while True: |
| 196 | result = [i.next() for i in iterables] |
| 197 | yield tuple(result) |
| 198 | \end{verbatim} |
| 199 | \end{funcdesc} |
| 200 | |
| 201 | \begin{funcdesc}{repeat}{obj} |
| 202 | Make an iterator that returns \var{obj} over and over again. |
| 203 | Used as argument to \function{imap()} for invariant parameters |
| 204 | to the called function. Also used with function{izip()} to create |
| 205 | an invariant part of a tuple record. Equivalent to: |
| 206 | |
| 207 | \begin{verbatim} |
| 208 | def repeat(x): |
| 209 | while True: |
| 210 | yield x |
| 211 | \end{verbatim} |
| 212 | \end{funcdesc} |
| 213 | |
| 214 | \begin{funcdesc}{starmap}{function, iterable} |
| 215 | Make an iterator that computes the function using arguments tuples |
| 216 | obtained from the iterable. Used instead of \function{imap()} when |
| 217 | argument parameters are already grouped in tuples from a single iterable |
| 218 | (the data has been ``pre-zipped''). The difference between |
| 219 | \function{imap()} and \function{starmap} parallels the distinction |
| 220 | between \code{function(a,b)} and \code{function(*c)}. |
| 221 | Equivalent to: |
| 222 | |
| 223 | \begin{verbatim} |
| 224 | def starmap(function, iterable): |
| 225 | iterable = iter(iterable) |
| 226 | while True: |
| 227 | yield function(*iterable.next()) |
| 228 | \end{verbatim} |
| 229 | \end{funcdesc} |
| 230 | |
| 231 | \begin{funcdesc}{takewhile}{predicate, iterable} |
| 232 | Make an iterator that returns elements from the iterable as long as |
| 233 | the predicate is true. Equivalent to: |
| 234 | |
| 235 | \begin{verbatim} |
| 236 | def takewhile(predicate, iterable): |
| 237 | iterable = iter(iterable) |
| 238 | while True: |
| 239 | x = iterable.next() |
| 240 | if predicate(x): |
| 241 | yield x |
| 242 | else: |
| 243 | break |
| 244 | \end{verbatim} |
| 245 | \end{funcdesc} |
| 246 | |
| 247 | \begin{funcdesc}{times}{n, \optional{object}} |
| 248 | Make an iterator that returns \var{object} \var{n} times. |
| 249 | \var{object} defaults to \code{None}. Used for looping a specific |
| 250 | number of times without creating a number object on each pass. |
| 251 | Equivalent to: |
| 252 | |
| 253 | \begin{verbatim} |
| 254 | def times(n, object=None): |
| 255 | if n<0 : raise ValueError |
| 256 | for i in xrange(n): |
| 257 | yield object |
| 258 | \end{verbatim} |
| 259 | \end{funcdesc} |
| 260 | |
| 261 | |
| 262 | \subsection{Examples \label{itertools-example}} |
| 263 | |
| 264 | The following examples show common uses for each tool and |
| 265 | demonstrate ways they can be combined. |
| 266 | |
| 267 | \begin{verbatim} |
| 268 | >>> for i in times(3): |
| 269 | ... print "Hello" |
| 270 | ... |
| 271 | Hello |
| 272 | Hello |
| 273 | Hello |
| 274 | |
| 275 | >>> amounts = [120.15, 764.05, 823.14] |
| 276 | >>> for checknum, amount in izip(count(1200), amounts): |
| 277 | ... print 'Check %d is for $%.2f' % (checknum, amount) |
| 278 | ... |
| 279 | Check 1200 is for $120.15 |
| 280 | Check 1201 is for $764.05 |
| 281 | Check 1202 is for $823.14 |
| 282 | |
| 283 | >>> import operator |
| 284 | >>> for cube in imap(operator.pow, xrange(1,4), repeat(3)): |
| 285 | ... print cube |
| 286 | ... |
| 287 | 1 |
| 288 | 8 |
| 289 | 27 |
| 290 | |
| 291 | >>> reportlines = ['EuroPython', 'Roster', '', 'alex', '', 'laura', |
| 292 | '', 'martin', '', 'walter', '', 'samuele'] |
| 293 | >>> for name in islice(reportlines, 3, len(reportlines), 2): |
| 294 | ... print name.title() |
| 295 | ... |
| 296 | Alex |
| 297 | Laura |
| 298 | Martin |
| 299 | Walter |
| 300 | Samuele |
| 301 | |
| 302 | \end{verbatim} |
| 303 | |
| 304 | This section has further examples of how itertools can be combined. |
| 305 | Note that \function{enumerate()} and \method{iteritems()} already |
| 306 | have highly efficient implementations in Python. They are only |
| 307 | included here to illustrate how higher level tools can be created |
| 308 | from building blocks. |
| 309 | |
| 310 | \begin{verbatim} |
| 311 | >>> def enumerate(iterable): |
| 312 | ... return izip(count(), iterable) |
| 313 | |
| 314 | >>> def tabulate(function): |
| 315 | ... "Return function(0), function(1), ..." |
| 316 | ... return imap(function, count()) |
| 317 | |
| 318 | >>> def iteritems(mapping): |
| 319 | ... return izip(mapping.iterkeys(), mapping.itervalues()) |
| 320 | |
| 321 | >>> def nth(iterable, n): |
| 322 | ... "Returns the nth item" |
| 323 | ... return islice(iterable, n, n+1).next() |
| 324 | |
| 325 | \end{verbatim} |