[Numpy-discussion] numpy.append & numpy.where vs list.append and brute iterative for loop
Christopher Barker
Chris.Barker at noaa.gov
Thu Jan 27 19:46:13 EST 2011
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
More information about the NumPy-Discussion
mailing list