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
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.
I initially wrote that thinking that the rotate duration would be
independent of the rotation distance, but...
>>> import timeit
>>> s = "from collections import deque; d = deque(xrange(1000000))"
>>> timeit.Timer(stmt="d.rotate(1)", setup = s).timeit(number=100000)
0.1372316872675583
>>> timeit.Timer(stmt="d.rotate(1000)", setup = s).timeit(number=100000)
3.5050192133357996
>>> timeit.Timer(stmt="d.rotate(10000)", setup = s).timeit(number=100000)
32.756590851630563
>>> timeit.Timer(stmt="d.rotate(100000)", setup = s).timeit(number=100000)
325.59845064107299
>>> timeit.Timer(stmt="d.rotate(999999)", setup = s).timeit(number=100000)
0.14491059617921564
Boy was I wrong. Given that it scales linearly it looks like it
cut-pastes the rotation an element at a time! At least it recognizes
the shortest rotation path, though.
On first guess of how the deque is implemented I would have thought
that rotation could be achieved simply by diddling some pointers, but I
could see how that would mess with popping efficiency (seems you'd have
to remap memory in the event of a pop after rotation). Worst case I
figured a rotate would just do a single shot memory remapping of the
deque contents so that the speed was the same regardless of rotation
size...
My guessing/figuring skills clearly need some work.
What's up with this deque rotation? If I were to hazard one more guess
I'd think it is trying to conserve transient memory usage during
rotation... in my (poor) mental scheme it seems that cutting/relocating
could take 50% more memory than the deque itself for a full rotation.
I should stop guessing. Or at least figure out how to find the source
code for the deque implementation...
Should I avoid using deques with large iterables?
Thanks,
Russ
--
http://mail.python.org/mailman/listinfo/python-list
