Deleting the first element of a list

[Peter Hansen]

Chad Netzer wrote:
> On Wednesday 02 October 2002 21:26, Bruce Dawson wrote:
> 
>>Highly applicable to this thread. Deleting the first item of a Python
>>list or C++ vector is an O(n) operation - proportional to the number
>>of items in the list. If you do that for every item in the list it is
>>O(n^2) - proportional to the square.
> 
> Here are the results on my machine:
...
> avg time to delete list of length       4096: 0.0555817842484 secs
...
> 
> And if I change the 'del l[ 0 ]' to 'del l[ -1 ]':
...
> avg time to delete list of length       4096: 0.0080970048904 secs
...
> Here a doubling of list length leads more or less to a doubling of 
> running time (ie.  O( N )).
> 
> So, no real surprises, but illustrative for those who have never 
> compared O( N^2 ) to O( N ) algorithms before (hmmm, maybe that should 
> be phi( N ) or even o( N )? )  I didn't dare do a longer list for 'del 
> l[ 0 ]', whereas 'del l[ -1 ]' scales easily to much longer lists.

Nice analysis.  I find it equally illustrative, for those who
always jump to optimization too quickly, to note that for any
value of N up to at least 4096 in your example, the difference
could well be completely below the threshold of noticability for
anything involving, for example, human response times.

Depending entirely on the particular case in which it is going to be
used, it is quite possible that spending more than ten seconds on the
whole issue ends up being wasted time.  Maybe the list will never
have more than 100 items, or maybe it has 16000 but it runs once a
day and nobody will be sitting waiting for it.

All the emphasis on algorithmic performance improvements is interesting,
but practically none of this should ever be an issue until somebody
is actually *bothered* by the performance once the system is running,
at least in testing.  (Well, that might be overstating it a little:
in some environments making changes that late in the game is dangerous,
but I guess I'm coming from an agile environment and optimization just
doesn't seem to be an issue these days, even with Python.)

-Peter