Popping from the middle of a deque + deque rotation speed
Tim Peters
tim.peters at gmail.com
Fri Apr 28 23:37:08 EDT 2006
[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 ;-)
More information about the Python-list
mailing list