The REALLY bad thing about Python lists ..

[Thomas Wouters]

On Mon, May 15, 2000 at 09:01:37AM -0500, Russell Turpin wrote:
> 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.

CPU is cheaper than memory, and grows faster (both in speed and in
quantity). Using too much memory is suboptimal as well.

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

Perhaps your test was just realistic ? Have you seen *real-life* performance
problems because of the low overallocation yet ?

-- 
Thomas Wouters <thomas at xs4all.net>

Hi! I'm a .signature virus! copy me into your .signature file to help me spread!