Re: obtaining the reversal of a sequence?

Guido.van.Rossum@cwi.nl
Thu, 21 Oct 1993 10:18:33 +0100

> I've encountered the problem where I'd like to have a sequence that is
> traversed in both directions equally frequently. It's a display list, and
> is traversed from back to front, to paint the window, and from front to
> back, to find the innermost element enclosing a point.
>
> Clearly, the ``for foo in x'' construct works well for one of the two
> cases, but what's the efficient way to traverse the list in reverse order?
> The best I can come up with is:
>
> tmp = list[:]
> tmp.reverse()
> for x in tmp:
> blah...
>
> and that's so inefficient I believe there must be some trick tucked away
> to make this easier.

Hmm, I don't think there's a trick for this in the language. You
could reverse the list in place and reverse it back after the loop --
reverse() is actually pretty fast compared to doing anything in
Python, and it's certainly faster than the code given here: the
list[:] operation will take more time than an extra reverse() call
because (a) it allocates two new blocks of memory, (b) it has to
increment the reference counts of all list items, and (c) it has to
undo all that when you're done.

Alternatively, if you can't afford to reverse the list in place
because other users of it may get confused, you can construct the
reverse index sequence manually:

i = len(list)
while i > 0:
i = i-1
x = list[i]
blah...

Using range() will create a list containing lots of new integer
objects and thus be the slowest of all, unless the list changes
infrequently and you can save a permanent copy of it -- but that's a
maintenance nightmare.

--Guido van Rossum, CWI, Amsterdam <Guido.van.Rossum@cwi.nl>