[Tutor] why is list.pop(0) slow? [swap-with-last-element trick]

[Gus Tabares]

I know I missed Wari's original e-mail to the list, but what about this:

>>> def removeFront(list):
	item = list[0]
	del list[0]
	return item

>>> list = [4, 5, 6, 7, 8]
>>> removeFront(list)
4
>>> list
[5, 6, 7, 8]

Is this considered 'bad' coding? I'd just thought I'd throw this out there,
see what the thoughts are.


/Gus



-----Original Message-----
From: tutor-admin@python.org [mailto:tutor-admin@python.org]On Behalf Of
Danny Yoo
Sent: Wednesday, June 18, 2003 6:36 PM
To: Wari Wahab
Cc: tutor@python.org
Subject: Re: [Tutor] why is list.pop(0) slow? [swap-with-last-element
trick]




> On Thu, 19 Jun 2003, Wari Wahab wrote:
>
> > I've been playing around with very large lists and found out by chance
> > that pop(0) is 8 times slower than pop(). Is it really that bad?

Hi Wari,


By the way, if the order of your elements is not important, then there's a
cute trick we can employ to remove elements from the front of a list: we
can swap the first and last elements, and then do a pop() off then end of
our list, because popping at the end is quite efficient.


###
>>> def removeFront(L):
...     L[-1], L[0] = L[0], L[-1]
...     return L.pop()
...
>>> mylist = range(10)
>>> mylist
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> removeFront(mylist)
0
>>> mylist
[9, 1, 2, 3, 4, 5, 6, 7, 8]
>>> removeFront(mylist)
9
>>> mylist
[8, 1, 2, 3, 4, 5, 6, 7]
###

We can generalize this swap-with-last-element trick to do "deletes"
anywhere in our list.  Notice, though, that the list will inevitably get
out of order when we do the swap-with-last-element trick: the
applicability of this technique really depends on the program we're
writing.  It might not be the right thing to do if we want to maintain the
relative order of things in our list.


If you can tell us more details about what you're expecting to do with
your lists (lots of deletes, lots of inserts, etc.), we can probably chat
about efficiency issues on Python-Tutor.


_______________________________________________
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor