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