[Python-Dev] deque alternative (was: Linked lists)

[Josiah Carlson]

Tim Peters <tim.peters at gmail.com> wrote:
> Like Phillip Eby, I use 2-tuples for this when I feel the need
> (usually during a backtracking graph search, to keep track of paths
> back to the root in a space-efficient way), and am happy with that.

Then there's the whole Python list with append() and pop().  It takes a
method resolution and function call, but at least in Python 2.3, it is a
hair faster...

 - Josiah

>>> if 1:
...     t = time.time()
...     a = tuple()
...     for i in xrange(1000000):
...             a = (i, a)
...     for i in xrange(1000000):
...             i,a = a
...     print time.time()-t
...
3.28500008583
>>> if 1:
...     t = time.time()
...     a = []
...     for i in xrange(1000000):
...             a.append(i)
...     for i in xrange(1000000):
...             i = a.pop()
...     print time.time()-t
...
3.02399992943