The REALLY bad thing about Python lists ..
noone at do.not.use
Mon May 15 21:34:59 CEST 2000
Moshe Zadka wrote:
> In other words, Python optimizes for the common
> case (lists of <10,000 elements) pretty well. ..
It turns out that it doesn't so much optimize, as happen
to be doubly lucky. On Linux, the realloc() procedure
does the smart thing.
There really is NO excuse for constant space allocation.
It does not save significant space, and it costs
considerable time. Here is what happens when creating an
array of length n:
Extend by K elements: O(n) O(n^2)
Extend by factor of F: O(n) O(n)
The second strategy wins hands down. If you want to
argue for the first strategy on the grounds that it
saves space, keep in mind (a) that the space savings
is only in the proportionality factor, not in the
complexity, and (b) this factor can be made as small
as desired by choosing a smaller expansion factor, F.
If you want to argue for the first strategy on the
grounds that it doesn't matter for small n, well ..
that is true for almost all algorithms, and would
really inhibit the use of Python for real applications,
where n gets to be large. If Python behaved this way
for my applications, I would have ditched it already.
Python doesn't behave that way for my applications
only because they run under Linux. On Linux, memory
blocks come in exponential increments, and realloc()
does nothing if the new request fits into the block
already allocated. This turns the first strategy into
the second strategy, and most of the memory extensions
Python performs on Linux are turned into no-ops! On
Windows, Python's choice of the first strategy shines
through, making it inappropriate for some real
applications. So really the issue is:
Should Python lists be as fast on other platforms
as they are on Linux, where good OS memory
management turned the second strategy into the
Personally, I think those who have to develop under
Windows suffer enough already, and they should at
least enjoy the same reasonably fast Python as the
rest of us!
This raises an interesting Linux question: Does it
use a buddy-list algorithm for memory management?
More information about the Python-list