The REALLY bad thing about Python lists ..

[Jeff Petkau]

Remco Gerlich <scarblac-spamtrap at pino.selwerd.nl> wrote in message
news:slrn8hu5nl.2s0.scarblac-spamtrap at flits104-37.flits.rug.nl...
> Appending is O(n^2) in theory, though, since the list has to be resized
(and
> copied) every once in a while. In practice this effect is minimal, of
> course...

If you grow the list exponentially (eg. double the size each time you have
to reallocate), then appending takes amortized constant time, so appending
up an entire list is O(n).

The question is, does Python do this? I looked in listobject.c, and it
appears
not. If the list has less that 500 elements, it grows 10 elements at a time;
more than 500 and it grows 100 elements at a time.

I fiddled around with timing tests (1.5.2 on Windows) to see what
Python's actual behavior is. If you're adding to a single list, it often
is linear, because the list is grown with realloc() which can get
lucky and just extend the size of the allocated block without having
to move it. But if you're allocating other stuff while building your list,
or
building two lists in parallel, realloc() doesn't get so lucky and growing
the list is O(N^2).

I'd consider this a bug in Python.

ps. why does it take amortized constant time? Well, suppose we've got
N elements in the list already. We append another N elements one at
a time. Since this doubles the list size, there will be just one
reallocation,
in which we'll have to copy at most 2N elements. So on average each element
requires O(2N/N) = O(1) time.

--Jeff