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

[Magnus Lyckå]

At 14:11 2003-06-19 -0700, Danny Yoo wrote:
>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."""
[snip]

This was interesting. Maybe I should actually read my Knuth,
not just let it look good and collect dust in the book shelf...
I guess I got a bit annoyed by his imaginary processor and
it's obscure assembler, and little jokes such as including
an exercise where you're supposed to prove Fermat's Theorem.
(I also like my thin old Aho, Hopcroft, Ullman.)

I did a quick comparision between Danny's class and a naive
pop(0) based implementation thoigh. See code below.

I just push a range of ints and then pop them. See the test
function below. Note the dummy test. This is needed, since the
first test run in the profiler has an extra overhead of 0.3
CPU seconds or so on my computer!!! Is it loading a module?

In my test, Danny's class is faster at about 2 000 elements.
At 30 000 elements, it's about four times faster, and the
difference will continue to grow.

class Queue1:
     """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()

class Queue2:
     def __init__(self):
         self._stack = []
     def push(self, obj):
         self._stack.append(obj)
     def pop(self):
         return self._stack.pop(0)

def test(q, n):
     for i in range(n):
         q.push(i)
     for i in range(n):
         q.pop()

def dummy():
         pass

import profile, sys

n = int(sys.argv[1])
profile.run('dummy()')
profile.run('test(Queue1(), %i)' % n)
profile.run('test(Queue2(), %i)' % n)



--
Magnus Lycka (It's really Lyckå), magnus@thinkware.se
Thinkware AB, Sweden, www.thinkware.se
I code Python ~ The Agile Programming Language