Deleting the first element of a list

[Bruce Dawson]

Peter Hansen wrote:

> Erik Max Francis wrote:
> 
>> JB wrote:
...
>> quantitative information about where the bottlenecks truly are.  This
>> concept is especially powerful in a high-level language like Python; the
>> very choice of using Python means that you're willing to trade raw speed
>> for flexibility.  If you're overconcerned with squeezing every last bit
>> of CPU power right from the start, then Python (or any other high-level
>> language) was probably not a good choice of languages.
> 
> 
> Well stated, although a note about changing algorithms generally
> providing the most significant speedups might be in order.  Even
> with Python, picking a better algorithm can produce huge gains.
> (This does not, of course, apply to a small idiomatic choice such
> as this thread was about.)


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.

The thing about O(n^2), and any complexity higher than that, is that 
there are many values of N that are small enough for N items to easily 
fit into memory, but large enough to make the program run for days and 
days and days and days.

O(n^2) is bad, unless you know that n will always be small.

So, if performance is a problem, the OP should consider reworking the 
code. For instance, if the original code was:

while myList:
     # Do Something with the first element
     del myList[0]

Then it should be much better to go:

myList.reverse()
while myList:
     # Do Something with the last element
     del myList[len(myList)-1]

This changes it from O(n^2) to O(n), which could make it run thousands 
of times faster.

Premature optimization is the root of all evil, but O(n^2) is pretty 
darned evil too!

Of course, the OP's code may not be so easily reworked as my simple example.