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 _______________________________________________ NumPy-Discussion mailing list [email protected] http://mail.scipy.org/mailman/listinfo/numpy-discussion
