The REALLY bad thing about Python lists ..
Russell Turpin
noone at do.not.use
Mon May 15 11:04:57 EDT 2000
Thomas Wouters wrote:
> Perhaps your test was just realistic ? Have you seen
> *real-life* performance problems because of the low
> overallocation yet ?
I've written MANY real-life programs that built up
two or more large arrays. Large, meaning over 100,000
elements. An O(n^2) cost to doing this would make
Python unusable for quite a few real-life applications.
HOWEVER .. it may be that Python is twice lucky. I
suspect that the realloc() on Linux does the smart
thing: allocating exponentially increasing blocks, as
needed, and expanding within the block if possible.
I have not been able to demonstrate O(n^2) behavior
for list allocation in test programs. If anyone can
do this, I would be interested in seeing the test
program.
Russell
More information about the Python-list
mailing list