no shift/unshift?

[Michael P. Soulier]

On Fri, 21 Feb 2003 15:33:12 -0800, Erik Max Francis <max at alcyone.com> wrote:
> 
> Use L.insert(0, x) and del L[x].  Remember that since Python lists are
> implemented as CS vectors, you suffer from O(n) penalties from
> manipulating the left side of the list rather than the right.  If you
> expect your sequences to be really long (where these penalties will
> really add up), you might want to consider writing your own linked list
> class.

    I didn't know much about the underlying implementation. Lets do a test...

#!/usr/bin/python

import time

list = range(10)

stime = time.time()
for i in xrange(1000000):
    list.append(i)
    list.pop()
etime = time.time()

print "Finished first loop in %f seconds." % (etime - stime)

stime = time.time()
for i in xrange(1000000):
    list.insert(0, i)
    list.pop(0)
etime = time.time()

print "Finished second loop in %f seconds." % (etime - stime)

[msoulier at piglet msoulier]$ ./bench.py 
Finished first loop in 8.207944 seconds.
Finished second loop in 10.413478 seconds.
[msoulier at piglet msoulier]$ ./bench.py 
Finished first loop in 8.146216 seconds.
Finished second loop in 9.120505 seconds.
[msoulier at piglet msoulier]$ ./bench.py 
Finished first loop in 9.507626 seconds.
Finished second loop in 9.125624 seconds.

    Well, the second loop takes longer to be sure, but not by much. 

    Mike

-- 
Michael P. Soulier <msoulier at digitaltorque.ca>, GnuPG pub key: 5BC8BE08
"...the word HACK is used as a verb to indicate a massive amount
of nerd-like effort."  -Harley Hahn, A Student's Guide to Unix
HTML Email Considered Harmful: http://expita.com/nomime.html