Popping from the middle of a deque + deque rotation speed

[Russell Warren]

> 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)
0.14770257113683627
>>> timeit.Timer(stmt="x=d[100000]", setup = s).timeit(number=100000)
1.4016418287799155

Russ