The REALLY bad thing about Python lists ..
jpet at eskimo.com
Tue May 16 03:07:47 EDT 2000
> [Jeff Petkau, on Python's conservative over-allocation when growing
> a list]
> > 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.
Mea culpa. I tried to reproduce my own tests, so I could
post the code and timings here and get someone to compare
it on Linux, and I couldn't. I was doing this in my test loop:
... list1 = 
... list2 = 
... for i in xrange(size):
Given the way integers are allocated, this biases the test
badly against long lists. Oops. With a fixed test (appending
0 instead of i) I could not get bad behavior for append, up
to 10M elements. I guess realloc on Windows is pretty
clever after all.
I still think exponential reallocation is the right way to do it,
but since I can't produce an actual problem case, I'll just
quietly shuffle away now.
--Jeff (jpet at eskimo.com)
More information about the Python-list