Iteration index

[D-Man]

On Fri, Jun 01, 2001 at 07:13:24PM +0000, E. Mark Ping wrote:
| In article <mailman.991336497.10877.python-list at python.org>,
| D-Man  <dsh8290 at rit.edu> wrote:
| >Yes, but I think
| >
| >s = ('a', 'b', 'ala', 'a')
| >for i in xrange( len( s ) ) :
| >    print i , s[i]
| >
| >is easier to read, and you don't have the chance of forgetting to
| >increment the counter.
| 
| Agreed.  But does it introduce n^2 complexity?  I can't find anything
| in the python docs that says that indexing into a list is O(1)--and
| most people assume that indexing into a list is O(n).

Does it really matter?  Either way you are indexing the same list --
the for loop indexes it automatically or you index it explicitly.

It is probably O(n) because it is a linked structure and indexing
isn't a computed offset (like C arrays) and it isn't a dict (hashing).
(Even if I am wrong in my guess on the list implementation, the index
is a runtime calculation, not a compiler-computed-and-now-hardcoded
jump from a known memory location).

-D