Velocity Reviews > Iteration over Lists and Strings

# Iteration over Lists and Strings

DeepBleu
Guest
Posts: n/a

 08-28-2004
I noticed the following:
>>a = 'abba'
>>for n in a:
>> print n, a.index(n)

a 0
b 1
b 1
a 0

(expected result:
a 0
b 1
b 2
a 3)

The same with lists:
>>List = [1, 0 , 1]
>>for n in List:
>> print n, List.index(n)

1 0
0 1
1 0

(expected result:
1 0
0 1
1 2)

What is going on? Can someone clarify this to me? And how can I ensure
that the iteration produces the absolute index number **without** doing
something like:
>>a = 'abba'
>>k = len(a)
>>for m in range(0, k):
>> print a[m], m

a 0
b 1
b 2
a 3

Thanks -

Andrew Durdin
Guest
Posts: n/a

 08-28-2004
On Sat, 28 Aug 2004 03:22:48 GMT, DeepBleu <(E-Mail Removed)> wrote:
> What is going on? Can someone clarify this to me? And how can I ensure
> that the iteration produces the absolute index number **without** doing
> something like:
> >>a = 'abba'
> >>k = len(a)
> >>for m in range(0, k):
> >> print a[m], m

The index() method looks up the first index of the given object in the
list/sequence. What you want is to use the enumerate() builtin:

>>>a = 'abba'
>>>for i, c in enumerate(a):

.... print c, i
....
a 0
b 1
b 2
a 3

Michel Claveau - abstraction méta-galactique non triviale en fuite perpétuelle.
Guest
Posts: n/a

 08-28-2004
and enumerate is more fast than index.

Alex Martelli
Guest
Posts: n/a

 08-28-2004
DeepBleu <(E-Mail Removed)> wrote:

> I noticed the following:
> >>a = 'abba'
> >>for n in a:
> >> print n, a.index(n)

> a 0
> b 1
> b 1
> a 0

a.index(n) returns the FIRST index x of a such thatn a[x]==n.

> (expected result:
> a 0
> b 1
> b 2
> a 3)

Misfounded expectation. The first 'b' and the second 'b' are equal, for
example, so a.index can never possibly return different results for
them.

> What is going on? Can someone clarify this to me? And how can I ensure
> that the iteration produces the absolute index number **without** doing
> something like:
> >>a = 'abba'
> >>k = len(a)
> >>for m in range(0, k):
> >> print a[m], m

> a 0
> b 1
> b 2
> a 3

That's what the enumerate built-in is for:

for m, n in enumerate(a):
print n, m

Alex

Alex Martelli
Guest
Posts: n/a

 08-28-2004
Michel Claveau - abstraction méta-galactique non triviale en fuite
perpétuelle. <(E-Mail Removed) m> wrote:

> and enumerate is more fast than index.

Oh, absolutely. sequence.index(anitem) takes time proportional to
len(sequence), for the average item. If you repeat that operation for
all items in sequence, you end up with total time proportional to the
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).

If you're familiar with big-O notation, we're talking O(N) vs O(N
square)... not the kind of performance issue one can ignore, for long
sequences, because the difference in performance keeps going up and up
without bounds as the sequence grows longer.

Alex

Terry Reedy
Guest
Posts: n/a

 08-28-2004

"DeepBleu" <(E-Mail Removed)> wrote in message
news:cUSXc.56768\$(E-Mail Removed)...
> (expected result:

When something does not act as expected, look in the manual or try the
builtin help facility, which only takes seconds.

>>> help(list.index)

Help on method_descriptor:

index(...)
L.index(value) -> integer -- return index of first occurrence of value

dir(object) will give you a list of attributes and methods. You can look
up new ones the same way. In particular, dir(list) and dir(__builtins__).

Terry J. Reedy

DeepBleu
Guest
Posts: n/a

 08-28-2004
Thanks all.

Brent W. Hughes
Guest
Posts: n/a

 08-28-2004

"Alex Martelli" <(E-Mail Removed)> wrote in message
news:1gj80xs.1cfownoqz4m9N%(E-Mail Removed)...
> Michel Claveau - abstraction méta-galactique non triviale en fuite
> perpétuelle. <(E-Mail Removed) m> wrote:
>
> > and enumerate is more fast than index.

>
> Oh, absolutely. sequence.index(anitem) takes time proportional to
> len(sequence), for the average item. If you repeat that operation for
> all items in sequence, you end up with total time proportional to the
> 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).
>
> If you're familiar with big-O notation, we're talking O(N) vs O(N
> square)... not the kind of performance issue one can ignore, for long
> sequences, because the difference in performance keeps going up and up
> without bounds as the sequence grows longer.
>
>
> Alex

Did you say enumerate(seq) takes constant time? I would have thought it was
proportional to len(seq).

Marc 'BlackJack' Rintsch
Guest
Posts: n/a

 08-28-2004
In <5M4Yc.326126\$a24.276550@attbi_s03>, Brent W. Hughes wrote:

> Did you say enumerate(seq) takes constant time? I would have thought it was
> proportional to len(seq).

>>> seq = [1,2,3]
>>> enumerate(seq)

<enumerate object at 0x4039dcec>

I guess creating a enumerate object (generator) takes constant time.

Ciao,
Marc 'BlackJack' Rintsch

Andrew Durdin
Guest
Posts: n/a

 08-28-2004
On Sat, 28 Aug 2004 19:09:53 GMT, Brent W. Hughes
<(E-Mail Removed)> wrote:
>
> Did you say enumerate(seq) takes constant time? I would have thought it was
> proportional to len(seq).

enumerate(seq) is O(1)
index(seq) is O(N)

And thus:

for i, val in enumerate(seq): print i is O(N)
for val in seq: print seq.index(val) is O(N*N)