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...
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...
.... 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)).... from collections import deque
.... class mydeque(deque):
.... def popmiddle(self, pos):
.... ret = self[pos]
.... del(self[pos])
.... return ret
.... d = mydeque(xrange(1000000))
.... """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

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.