[Tutor] why is list.pop(0) slow? [heapq in Python 2.3 / Queues with Stacks]

[Danny Yoo]

> >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.
>
> Well, I've managed to solve these issues by:
>
>  * Not caring about speed :) (Yeah, we'll wait for 18 months more for
>    speeds to double up)
>  * Used a queue and heap data structures for priorities as well as a
>    FIFO style store.

Hi Wari,


Sounds good.  The Standard Library will actually include a new 'heapq'
module soon:

    http://www.python.org/dev/doc/devel/lib/module-heapq.html


So if you are doing that pop/push work to implement a priority queue, you
might be able to just yank the 'heapq' module out of Python 2.3 and make
it work in Python 2.2.




As a random note: there's a very concise and cute way of efficiently
implementing a FIFO Queue by using two Stacks.  Python's Lists act
marvelously as a stack-like data structure, and it's kinda cool to see
that we can get an efficient Queue out of them:

###
>>> class Queue:
...     """A sample implementation of a First-In-First-Out
...        data structure."""
...     def __init__(self):
...         self.in_stack = []
...         self.out_stack = []
...     def push(self, obj):
...         self.in_stack.append(obj)
...     def pop(self):
...         if not self.out_stack:
...             while self.in_stack:
...                 self.out_stack.append(self.in_stack.pop())
...         return self.out_stack.pop()
...
>>> q = Queue()
>>> q.push("a")
>>> q.push("b")
>>> q.push("c")
>>> q.pop()
'a'
>>> q.push("d")
>>> q.pop()
'b'
>>> q.pop()
'c'
>>> q.pop()
'd'
>>> q.push("e")
>>> q.push("f")
>>> q.pop()
'e'
>>> q.pop()
'f'
>>> q.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 13, in pop
IndexError: pop from empty list
###


And this implementation does pop(0) in constant time: it'll be fast,
regardless of the size of our input.  The above queue implementation is
pretty standard in Computer Science literature.  (It's Exercise 14 in
TAOCP Section 2.2.1.)  So even if lists, by themselves, don't support
pop(0) efficiently, with a little knowledge, we can bend them to do pop(0)
fast.


Hope this helps!