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

[Sturla Molden]

Den 28.01.2011 00:33, skrev Christopher Barker:
>
> hmmm - that doesn't seem quite right -- lists still have to 
> re-allocate and copy, they just do it every n times (where n grows 
> with the list), so I wouldn't expect exactly O(N).

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). The advantage of this implementation over linked lists 
is that indexing will be O(1) as well.

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.

Sturla