[Tutor] speeding code along [lists and dictionaries are fast]

[Magnus Lycka]

At 11:19 2002-11-18 -0700, Bob Gailer wrote:
>I don't know how python manages lists internally

AFAIK, it's basically an array of pointers. This means
that item look-up is fast regardless of the size of the
list. Basically, the base address of the list and the
list index tells you where you find the address on the
heap to the object you are looking for. Adding and removing
objects in the end of the list is also fast. Modifying
the beginning of a large list (del l[0], l.insert(0,0) etc)
is on the other hand slow, since the whole array needs to
be moved. (Actually, on "del l[0]" one could just move the
base adress! But I don't think it works that way. :)

I haven't looked at the internals of lists, but they behave
as if they would be implemented as I write here, as you can
easily verify with some timing tests. In reality it's probably
a bit more complex.


-- 
Magnus Lycka, Thinkware AB
Alvans vag 99, SE-907 50 UMEA, SWEDEN
phone: int+46 70 582 80 65, fax: int+46 70 612 80 65
http://www.thinkware.se/  mailto:magnus@thinkware.se