Efficiently iterating over part of a list

Duncan Booth duncan.booth at invalid.invalid
Fri Oct 13 10:42:40 CEST 2006


Steven D'Aprano <steve at REMOVEME.cybersource.com.au> wrote:

> The important thing to notice is that alist[1:] makes a copy. What if
> the list has millions of items and duplicating it is expensive? What
> do people do in that case?

I think you are worrying prematurely.

On my system slicing one element off the front of a 10,000,000 element list 
takes 440mS. The same operation on 1,000,000 elements taks 41mS. Iterating 
through the sliced list:

for x in r[1:]:
   y = x+1

takes 1.8s and 157mS respectively, so the slicing is only a quarter of the 
time for even this minimal loop. As soon as you do anything much inside the 
loop you can forget the slice cost.

Remember that copying the list never copies the elements in the list, it 
just copies pointers and bumps ref counts. Copying a list even if it has 
millions of items is not usually expensive compared with the costs of 
manipulating all the items in the list.

So the first thing you do is not to worry about this until you know it is 
an issue. Once you know for a fact that it is a problem, then you can look 
at optimising it with fancy lazy slicing techniques, but not before.



More information about the Python-list mailing list