Popping from the middle of a deque + deque rotation speed

[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

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

[Tim Chase]

> 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

My first thought would just be to use indexing:

def popmiddle(self, pos):
ret = self[pos]
del(self[pos])
return ret

It seems to work with my Python2.4 here. If you're
interested in efficiency, I'll leave their comparison as an
exercise to the reader... :)

-tkc

[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 ;-)

[Russell Warren]

Thanks for the responses.

It seems to work with my Python2.4 here. If you're
interested in efficiency, I'll leave their comparison as an
exercise to the reader... :)

Ok, exercise complete! :) For the record, they are pretty much the
same speed...

s = """ .... from collections import deque
.... class mydeque(deque):
.... def popmiddle(self, pos):
.... self.rotate(-pos)
.... ret=self.popleft()
.... self.rotate(pos)
.... return ret
.... d = mydeque(xrange(1000000)) timeit.Timer(stmt="x=d.popmiddle(1000)", setup = s).timeit(number=100000) 5.4620059253340969 s2=""" .... from collections import deque
.... class mydeque(deque):
.... def popmiddle(self, pos):
.... ret = self[pos]
.... del(self[pos])
.... return ret
.... d = mydeque(xrange(1000000))
.... """ timeit.Timer(stmt="x=d.popmiddle(1000)", setup = s2).timeit(number=100000)

5.3937888754018104

Thanks for the alternative solution.

Russ

[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

[Tim Peters]

[Russell Warren]

...
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.

FYI, deque implements efficient forward and reverse iterators. So, e.g.,

for x in a_deque:
pass

and

for x in reversed(a_deque):
pass

takes time proportional to len(a_deque). In contrast,

for i in xrange(len(a_deque)):
x = a_deque[i]

take time quadratic in len(a_deque).

The iterators don't use __getitem__ under the covers; explicitly
indexing does, and that's the difference here.