Python Reverse Generator

I'm looking for a way to reverse a generator object. I know how to reverse sequences:

foo = imap(seq.__getitem__, xrange(len(seq)-1, -1, -1))

But is something similar possible with a generator as the input and a reversed generator as the output (len(seq) stays the same, so the value from the original sequence can be used)?

13.10.2009 16:04:24
I have to take exception with your example of reversing a sequence. Why not just use reversed? or .reverse? Even seq[::-1] is clearer than what you wrote.
Steven Kryskalla 13.10.2009 16:18:49
Because all these examples will create a new list. My example above is the only way I know to create a list without copying it first.
ak. 13.10.2009 16:42:06
Well, I learned something new - seq[::-1] does in fact create a new list. See my generator expression answer for an alternative using negative indices.
PaulMcG 13.10.2009 17:41:01
ak - the reversed() function does not make a copy of the sequence, it works very similarly to your example. But as several people have mentioned, there is no way to do this on a generator without first copying the generator to a list.
Matt Good 14.10.2009 04:19:37
3 ОТВЕТА
РЕШЕНИЕ

You cannot reverse a generator in any generic way except by casting it to a sequence and creating an iterator from that. Later terms of a generator cannot necessarily be known until the earlier ones have been calculated.

Even worse, you can't know if your generator will ever hit a StopIteration exception until you hit it, so there's no way to know what there will even be a first term in your sequence.

The best you could do would be to write a reversed_iterator function:

def reversed_iterator(iter):
    return reversed(list(iter))

EDIT: You could also, of course, replace reversed in this with your imap based iterative version, to save one list creation.

26
13.10.2009 19:13:08
Strictly speaking, list(iter) is not a cast, it is the construction of a list by consuming the iterator iter. I'm not sure Python has any cast functions, at least not the in the sense that that term is used in languages like C or Java. int("100") is not a cast, and float(100) is not a cast - both are constructors that return objects. In C, if something is cast, the original object remains the same. If you did such a thing in Python, you could take the id of the original value, and the casted value, and they would be the same. In short: in Python, the cast is died.
PaulMcG 13.10.2009 16:28:25
@Paul McGuire: I agree with the important parts of what you said. One nit, though: in C, a cast can change the original object. If you cast 100 to float, C will change it to 100.0f; C will not simply throw the bit pattern 0x00000064 in to the float variable and let it turn into whatever value that would be in a float. In C, a cast can simply change type (change int * to long int *, or change int to long int) or can change value and type. C++ has several casting operators, including one that "reinterprets" type without changing the value at all.
steveha 13.10.2009 18:31:10
I agree with all this. My excperience with C is limited to running through a couple exercises in K&R, so I used the term cast loosely. I'd edit, but that would just cause confusion at this point. So instead, I'll give you an upvote.
jcdyer 13.10.2009 19:08:18
@steveha: Oh, sorry, you are correct in saying casting an int as float will do implicit promotion to float. I was thinking of this: int* intptr = new int(100); float* fltptr = (float*)intptr; printf("%e", *fltptr); /* no conversion of the actual value 100, so instead we get 1.401298e-043 */
PaulMcG 13.10.2009 19:29:48
@PaulMcGuire, I may misunderstand what you mean, but it is the case that in both a C cast and in a Python object-construction that the original value remains unchanged. Using float(i) in a C expression leaves i precisely unchanged, just as it leaves the original i object intact in Python. And the newly built object in Python will most certainly not have the same ID as the original value! Which can easily be demonstrated with: i = 1; float(i) is iFalse.
Brandon Rhodes 14.03.2014 22:12:07

reversed(list(input_generator)) is probably the easiest way.

There's no way to get a generator's values in "reverse" order without gathering all of them into a sequence first, because generating the second item could very well rely on the first having been generated.

6
13.10.2009 16:13:18

You have to walk through the generator anyway to get the first item so you might as well make a list. Try

reversed(list(g))

where g is a generator.

reversed(tuple(g))

would work as well (I didn't check to see if there is a significant difference in performance).

4
13.10.2009 16:13:19