Surprising (for me) benchmark results...
Courageous
jkraska1 at san.rr.com
Tue May 1 23:59:27 EDT 2001
>If you want to consider things that way then you have to worry
>about Python's list extension, which last I heard was O(N**2)...
NO.
list.append() appends items to a dynamic array in O(1)+k
constant amortized time. It does this by using a liberal preallocation
strategy, and leaving empty slots into which new elements can
be placed. The occasional realloc() amortizes away quite readily.
C//
More information about the Python-list
mailing list