The REALLY bad thing about Python lists ..

[Thomas Wouters]

On Mon, May 15, 2000 at 12:03:08AM +0000, Jeff Petkau wrote:

> 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. But if you're allocating other stuff while building your list,
> or
> building two lists in parallel, realloc() doesn't get so lucky and growing
> the list is O(N^2).
> 
> I'd consider this a bug in Python.

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. If you really need this speed,
and frequently double the lists size, either use extend or dont use lists
use arrays or write your own C extension to do the handling.

I doubt the common usage of list requires them to double in size whenever
you outgrow the previous allocation, but then I hardly use lists that large,
and when i do use them, i dont modify them much.

-- 
Thomas Wouters <thomas at xs4all.net>

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