[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 ;-) -- http://mail.python.org/mailman/listinfo/python-list
