array, list, performance...
Michael Chermside
mcherm at destiny.com
Thu Jun 6 09:11:52 EDT 2002
Here is my understanding of it:
li = [x0, x1, x2, ...]
li[n] element access is O(1)
li.append(x) appending is O(1)
(actually, it SOMETIMES takes O(len(li)) as it
resizes the list. But if you grow a list by
continually appending, the amortized time is
linear (ie, constant amortized time per element)
li.insert(0) prepending is O(len(li))
(so grow the list from the end!)
del li[0] deleting from the front (or middle) is O(len(li))
li.pop() deleting from the end is O(1)
li[n] = x assignment to the middle is O(len(li))
len(li) determining length is O(1)
li.index(x) search is O(len(li)) (NOT efficient)
li.sort() sort is O(len(li)*ln(len(li)))
(I believe it uses quicksort, but if a python
function has to be executed for the compare
that may take some time.)
It's really just your basic auto-growing array, but with a bunch of
clever things done to speed up common cases, and I don't know those well
enough to comment on them.
-- Michael Chermside
More information about the Python-list
mailing list