Popping from the middle of a deque + deque rotation speed

Russell Warren russandheather at gmail.com
Tue May 2 01:53:26 CEST 2006

> So does the speed of the remaining 0.001 cases really matter?  Note
> that even just indexing into a deque takes O(index) time.

It doesn't matter as much, of course, but I was looking to make every
step as efficient as possible (while staying in python).

As to indexing into a deque being O(index)... I didn't realize that.
It is certainly something to keep in mind, though... looping through
the contents of a deque would obviously be a bad idea with this being
the case!  I wonder if the generator for the deque helps reduce this?
Will check later.

Proof of the O(n) for indexing into a deque (not that I doubted Tim #2!

>>> import timeit
>>> s = "from collections import deque; d = deque(xrange(1000000))"
>>> timeit.Timer(stmt="x=d[10000]", setup = s).timeit(number=100000)
>>> timeit.Timer(stmt="x=d[100000]", setup = s).timeit(number=100000)


More information about the Python-list mailing list