[SciPy-user] How to start with SciPy and NumPy

Sturla Molden sturla@molden...
Mon Jan 26 09:36:47 CST 2009

> On Mon, Jan 26, 2009 at 11:52 PM, Sturla Molden <sturla@molden.no> wrote:

> So this is the well known method of over allocating when you need to
> grow, right ? This is not constant time, and depends on the number of
> items you are adding I think (sublinearly, but still)

Ok, I think you misunderstood:

- Adding one element to a Python list of length N is O(1) on average.

- Adding one element to a linked list of length N is O(1).

- In both bases, growing a list from length 0 to length N takes O(N) time.

For Python lists, if you know the size in advance, pre-allocation
certainly helps: [None]*N is much faster than [None for n in range(N)].
But both operations are actually of O(N) complexity. For linked lists,
pre-allocation is meaningless.

> I think that's how
>  array-based lists work, the array is just the address of the items,
> whereas for arrays, the address is the item.

That is correct.

But it may or may not matter. If the array list has pointers to cache
coherent objects, this double indirection has very little consequence for
the performance.


More information about the SciPy-user mailing list