Iteration over Lists and Strings

[Alex Martelli]

Brent W. Hughes <brent.hughes at comcast.net> 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...:

[a]

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

[b]

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;-)).


Alex