|Sent on:||Monday, August 16, 2010 4:05 PM|
|I'm pretty sure list.insert is not linear if you insert near the end of the list. |
I think lists overallocate a percentage
of space to allow n inserts near the end to have n log n
asymptotic performance. In fact
looking at the top of listobject.c in Python 2.7 I see:
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
On the other hand n calls to list.insert(0,x) has n**2 performance for n inserts because
all the elements in the internal array all have to be shifted for each insert.
So the moral is: If you need to add stuff to the front then build the list backwards
and reverse it. If you need to add stuff randomly, then you probably want to think
about using a dictionary somehow and then linearize it into a list later.
In theory Lisp cons cells are better for this kind of thing: in practice the
memory fragmentation kills you and python-style list/arrays are better
for what you usually need to do.
Sorry, couldn't keep my mouth shut. -- Aaron Watters
--- On Sat, 8/14/10, Jordan P <[address removed]> wrote: