The REALLY bad thing about Python lists ..

[Russell Turpin]

On Mon, May 15, 2000 at 12:03:08AM +0000, Jeff Petkau wrote:
>> I'd consider this a bug in Python.

Thomas Wouters wrote:
> 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. ..

Nope. Doubling the size of the array causes reallocation 
(and copying associated with it) to be O(n), even in the
bad cases. It's only inefficiency is space: sometimes 
the array consumes almost twice as much space as it 
requires. Given the importance of speed and cheapnesss
of memory, this is the right trade-off for everything,
except perhaps a palm virtual machine.

Damn! From my tests, I was hoping that Python was smart,
and it turns out, it is dumb, and the test was just
"lucky."

Russell