Popping from the middle of a deque + deque rotation speed

[Tim Peters]

[Russell Warren]
|> Does anyone have an easier/faster/better way of popping from the middle
> of a deque than this?
>
> class mydeque(deque):
>   def popmiddle(self, pos):
>     self.rotate(-pos)
>     ret = self.popleft()
>     self.rotate(pos)
>     return ret

As Tim Chase said, the easiest way is to do "del self[pos]" instead of
manually fiddling with rotations.  However, deque's implementation of
__delitem__ does rotations under the covers, so it's not necessarily
faster.

> I do recognize that this is not the intent of a deque, given the
> clearly non-"double-ended" nature.  I'm using a deque in a place where
> 99.999 of the time it will be a fifo, but occasionally I will want to
> pop from the middle.

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

> ...
> I should stop guessing.  Or at least figure out how to find the source
> code for the deque implementation...

It's in Modules/collectionsmodule.c.  You'll see that a deque is
implemented as a doubly-linked list of buckets, where each bucket is a
contiguous vector of no more than 62 (pointers to) elements.  There
appears to be an invariant that all "interior" (non-endpoint) buckets
contain exactly 62 elements, presumably to speed indexing.  It all
works very well for deque's intended purposes.

> Should I avoid using deques with large iterables?

Can't answer that without more detail about the criteria you use to judge ;-)