array, list, performance...

[Ype Kingma]

Michael Chermside wrote:
> 
> 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)

Append is often enough linear in the length of the list
that growing by appending is O(len(li) * len(li)).
You can prevent that by creating a list a large enough list
when starting, eg:

li = [None] * neededSize

>     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))

Assigment to the middle of a list is O(1), ie. same as element access.

>     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

Have fun,
Ype

-- 
email at xs4all.nl