Deleting the first element of a list

[Chad Netzer]

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.

Just for fun, I wrote this up:

N = 17
M = 5
for n in xrange(4,N):
    m = 5
    avg = 0
    for j in xrange( M ): 
        l = range( 2**n )
        start = time.time()
        for i in xrange( 2**(n-3) ):
            del l[ 0 ]
            del l[ 0 ]
            del l[ 0 ]
            del l[ 0 ]
            del l[ 0 ]
            del l[ 0 ]
            del l[ 0 ]
            del l[ 0 ]
        end = time.time()
        avg = avg + (end - start)
    avg = avg / m
    print "avg time to delete list of length %10d: %.13f secs" % (2**n, 
avg)

Here are the results on my machine:
avg time to delete list of length         16: 0.0000482082367 secs
avg time to delete list of length         32: 0.0000820159912 secs
avg time to delete list of length         64: 0.0001710176468 secs
avg time to delete list of length        128: 0.0003101825714 secs
avg time to delete list of length        256: 0.0006976127625 secs
avg time to delete list of length        512: 0.0017696142197 secs
avg time to delete list of length       1024: 0.0053425788879 secs
avg time to delete list of length       2048: 0.0166998147964 secs
avg time to delete list of length       4096: 0.0555817842484 secs
avg time to delete list of length       8192: 0.2105991840363 secs
avg time to delete list of length      16384: 0.9571284055710 secs
avg time to delete list of length      32768: 3.1392956018448 secs
avg time to delete list of length      65536: 25.6988666057587 secs

The last line I think shows the some effects of cache thrashing (but 
not swapping; I have 1 Gig of RAM).  It also illustrates each doubling 
of the problem set increases the running time by a factor of 4 or more 
(ie. ~ O( N^2 ) growth, at least when the lists start to get long (ie. 
> 512 items or so)

And if I change the 'del l[ 0 ]' to 'del l[ -1 ]':
avg time to delete list of length         16: 0.0000484228134 secs
avg time to delete list of length         32: 0.0000805854797 secs
avg time to delete list of length         64: 0.0001428127289 secs
avg time to delete list of length        128: 0.0002708435059 secs
avg time to delete list of length        256: 0.0005234003067 secs
avg time to delete list of length        512: 0.0010224103928 secs
avg time to delete list of length       1024: 0.0020072221756 secs
avg time to delete list of length       2048: 0.0040839672089 secs
avg time to delete list of length       4096: 0.0080970048904 secs
avg time to delete list of length       8192: 0.0164772510529 secs
avg time to delete list of length      16384: 0.0334905624390 secs
avg time to delete list of length      32768: 0.0808611869812 secs
avg time to delete list of length      65536: 0.1617539882660 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.

-- 

Chad Netzer
cnetzer at mail.arc.nasa.gov