[Numpy-discussion] numpy.append & numpy.where vs list.append and brute iterative for loop

[Christopher Barker]

On 1/27/11 3:54 PM, Sturla Molden wrote:
> Lists allocate empty slots at their back, proportional to their size. So
> as lists grows, re-allocations become rarer and rarer. Then on average
> the complexity per append becomes O(1), which is the "amortised"
> complexity. Appending N items to a list thus has the amortized
> complexity O(N).

I think I get that now...

> NumPy arrays are designed to be fixed size, and not designed to amortize
> the complexity of appends. So if you want to use arrays as efficient
> re-sizeable containers, you must code this logic yourself.

And I do get that. And yet, experimentally, appending numpy arrays (on 
that one simple example) appeared to be O(N). Granted, a much larger 
constant that for lists, but it sure looks linear to me.

Should it be O(N^2)? Maybe I need to run it for larger N , but I got 
impatient as it is.

-Chris


-- 
Christopher Barker, Ph.D.
Oceanographer

Emergency Response Division
NOAA/NOS/OR&R            (206) 526-6959   voice
7600 Sand Point Way NE   (206) 526-6329   fax
Seattle, WA  98115       (206) 526-6317   main reception

Chris.Barker at noaa.gov