Deleting the first element of a list

[Peter Hansen]

Alex Martelli wrote:
> Peter Hansen wrote:
>>Bruce Dawson wrote:
>>
>>>This changes it from O(n^2) to O(n), which could make it run thousands
>>>of times faster.
>>
>>You're making assumptions, possibly good ones, about the implementation
>>of the list object in Python.  It's possible, though obviously unlikely,
>>that the list is reallocated and copied every time it shrinks by even
>>one element.  (I'm just pointing this out for discussion purposes...
>>no doubt it doesn't work that way.)  That would leave it at O(n^2).
> 
> Python does not specify the O()-behavior of its built-in type's operations
> (the way C++'s standard library does), but I think I have the next best
> thing -- Tim Peters' review of my forthcoming Nutshell book's chapter on
> optimization, which does devote some time to documenting that behavior.
> For x>0, "del somelist[x]" is O(len(somelist)-x) -- you can count on
> that as well as you can count on most things in this sublunar orb.
> 
> IOW, I don't think these "discussion purposes" serve any concrete
> purpose in this context.

Sure they did... they brought out your nice response.  That is,
after all, what "discussion purposes" means. ;-)

> "del alist[0]" must copy N-1 references; "alist = alist[1]" must
> perform the same copies plus one allocation and one freeing.  So,
> the former's performance "can't" (with reasonable certainty) be
> worse than the latter's, but you can't predict how much better --
> surely not across platforms.  Still, if you must choose between
> the two ways of expressing functionality that is equivalent to
> your application, the former is clearly better.

Taking note again of Timothy Delaney's point that in fact the
functionality is *not* equivalent: del alist[0] will throw
an exception if the list is empty, while slicing will not.

I think this all just reinforces the claim that these choices
should generally be made on the basis of readability rather than
performance.

-Peter