Iteration over Lists and Strings

Alex Martelli aleaxit at
Mon Aug 30 09:05:09 CEST 2004

Brent W. Hughes < at> wrote:
> > SQUARE of len(sequence) -- a LOT, for long sequences,  enumerate itself
> > takes constant time, and looping over all items that enumerate yields
> > takes time proportional to the number of items (costant time per item).
> Did you say enumerate(seq) takes constant time?  I would have thought it was
> proportional to len(seq).

Please look carefully at my quoted text:
    the call to enumerate(seq) itself takes constant time
    looping over [N items] takes O(N)
In particular, looping over O(len(seq)) items does take O(len(seq)),
whether you call enumerate somewhere or not

The distinction matters, because some loops on enumerate(seq) may be
able to bail out earlier, which may reduce their big-O behavior.  A
trivial example:
    for i, item in enumerate(seq):
        if i >= 3: break
        print item
This prints the first few items of seq, but no more than three of them
in any case; and it takes O(1), constant time (assuming that so do
iter(seq)'s next(), and str(item) too) -- no matter how long seq is.

Don't take this for granted, because it was not necessarily true before
Python refined its looping protocol.  Consider two recipes  for
enumerate that you'll find in the Cookbook's first edition...:


class enumerate:
    def __init__(self, seq):
         self.seq = seq
    def __getitem__(self, i):
         return i, self.seq[i]


def enumerate(seq): return zip(xrange(sys.maxint), seq)

Recipe [a] does satisfy the same big-O performance constraints as
today's enumerate ([a] is less general than today's enumerate, of
course, because at that time the looping protocol did require the
ability to index into the object, so [a] requires that from seq).  But
recipe [b] does not -- just calling enumerate in this version is O(N) in
both time and space.  ((Nevertheless, [b] was faster than [a] in many
practically important cases, which is why I presented it anyway;-)).


More information about the Python-list mailing list