The REALLY bad thing about Python lists ..

[Jeff Petkau]

Thomas Wouters sez:
> On Mon, May 15, 2000 at 12:03:08AM +0000, Jeff Petkau wrote:
> > [jp] 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.

> [tw] Really ? Why ? The code isn't wrong, is it ? It's merely
> suboptimal in some cases. If lists were to double instead
> of grow by 100 elements, you would get suboptimal
> performance in other cases. If you really need this speed,
> and frequently double the lists size, either use extend or
> dont use lists use arrays or write your own C extension to
> do the handling.
>
> I doubt the common usage of list requires them to double in
> size whenever you outgrow the previous allocation, but then
> I hardly use lists that large, and when i do use them, i dont
> modify them much.

It's merely suboptimal, yes, but it's *severely* suboptimal in
the very common case of appending to a list, and a much better
solution is known. It's no different than if list.sort() was
O(N^2)--it's just a speed difference, but it's a huge one with
a well known good solution.

(Also, if you really can't stand the thought of lists
sometimes overallocating by a factor of 2, note that any
exponential growth will give you nice constant-time appends,
just with a higher constant. So you can grow by a factor of,
say, 1.25 instead. Saves a bit of memory but a bit slower.)

I wrote a patch for this last night. Now to figure out how to
send the thing in...

--Jeff (jpet at eskimo.com)