Python nested generators

Question

I was trying to implement the reverse function of itertools.izip on Python 2.7.1. The thing is that I find a problem, and I don't have an explantion. Solution 1, iunzip_v1 works perfectly. But solution 2. iunzip_v2, doesn't works as expected. Til now, I haven't found any relevant information about this problem, and reading the PEP about generators, it sound it should work, but it doesn't.

import itertools
from operator import itemgetter

def iunzip_v1(iterable):
    _tmp, iterable = itertools.tee(iterable, 2)
    iters = itertools.tee(iterable, len(_tmp.next()))
    return tuple(itertools.imap(itemgetter(i), it) for i, it in enumerate(iters))

def iunzip_v2(iterable):
    _tmp, iterable = itertools.tee(iterable, 2)
    iters = itertools.tee(iterable, len(_tmp.next()))
    return tuple((elem[i] for elem in it) for i, it in enumerate(iters))

result:

In [17]: l
Out[17]: [(0, 0, 0), (1, 2, 3), (2, 4, 6), (3, 6, 9), (4, 8, 12)]

In [18]: map(list, iunzip.iunzip_v1(l))
Out[18]: [[0, 1, 2, 3, 4], [0, 2, 4, 6, 8], [0, 3, 6, 9, 12]]

In [19]: map(list, iunzip.iunzip_v2(l))
Out[19]: [[0, 3, 6, 9, 12], [0, 3, 6, 9, 12], [0, 3, 6, 9, 12]]

Seems that iunzip_v2 is using the last value, so the generators aren't keeping the value while they are created inside the first generator. I'm missing something and I don't know what is.

Thanks in advance if something can clarify me this situation.

UPDATE: I've found the explanation here PEP-289, my first read was at PEP-255. The solution I'm trying to implement is a lazy one, so:

  zip(*iter) or izip(*...)

doesn't work for me, because *arg expand the argument list.

zip has to expand the argument list. The first element zip returns is the first element of each input argument. So it has iterated over the entire argument list. What you are doing with tee is creating a lot of copies of the input list. — Jochen Ritzel
– Jochen Ritzel, Commented Jun 22, 2011 at 1:00
First, @Andrés, don't call tuple at the end if you want a lazy implementation. — senderle
– senderle, Commented Jun 22, 2011 at 2:34
Second, @Jochen, Andrés' current implementation, if it didn't call tuple, would be lazy in the argument generator, but not in the arguments, which have a len and are therefore sequences. — senderle
– senderle, Commented Jun 22, 2011 at 2:36
Third, @Jochen, @Andrés, you can have an izip function that is lazy in the argument generator, or in the individual arguments, but not both. — senderle
– senderle, Commented Jun 22, 2011 at 2:37
@senderle: you're right, I can have both. My idea was to be lazy at the iunzip argument iterator, I am assuming that the tuples inside the argument generator aren't bigger. Thanks for your replies! — Andrés Moreira
– Andrés Moreira, Commented Jun 22, 2011 at 12:07

senderle · Accepted Answer · 2011-06-21 22:53:39Z

8

You're reinventing the wheel in a crazy way. izip is its own inverse:

>>> list(izip(*izip(range(10), range(10))))
[(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)]

But that doesn't quite answer your question, does it?

The problem with your nested generators is a scoping problem that happens because the innermost generators don't get used until the outermost generator has already run:

def iunzip_v2(iterable):
    _tmp, iterable = itertools.tee(iterable, 2)
    iters = itertools.tee(iterable, len(_tmp.next()))
    return tuple((elem[i] for elem in it) for i, it in enumerate(iters))

Here, you generate three generators, each of which uses the same variable, i. Copies of this variable are not made. Then, tuple exhausts the outermost generator, creating a tuple of generators:

>>> iunzip_v2((range(3), range(3)))
(<generator object <genexpr> at 0x1004d4a50>, <generator object <genexpr> at 0x1004d4aa0>, <generator object <genexpr> at 0x1004d4af0>)

At this point, each of these generators will execute elem[i] for each element of it. And since i is now equal to 3 for all three generators, you get the last element each time.

The reason the first version works is that itemgetter(i) is a closure, with its own scope -- so every time it returns a function, it generates a new scope, within which the value of i does not change.

edited Jun 21, 2011 at 22:53

answered Jun 21, 2011 at 22:45

senderle

152k36 gold badges218 silver badges244 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Andrés Moreira Over a year ago

Hi, first of all thanks to answer! The problem with your first solution is that izip(*izip(...)), the * expand the iterators before they will be used, and that is what I want to avoid. When I asked the question I read the PEP-255 "Simple generators", but the answer was on PEP-289 "Generator expressions" I've found this [python.org/dev/peps/pep-0289/…. As you said my confusion is with the evaluation and execution order. Thanks a lot for your reply!

senderle Over a year ago

@Andrés, so what I understand you to be saying is that you want not an "iunzip", but an izip that unpacks an argument generator lazily, given that the elements in the generator are already sequences. That works, but as I say above, don't call tuple at the end in that case.

Andrés Moreira Over a year ago

as I replied above, I am assuming the tuples of the argument iterator aren't bigger, so in this case, I call tuple with that "precondition".

senderle Over a year ago

@Andrés, ok, I think I misunderstood your intent. My point was just that you could be a little lazier with return ((elem[i] for elem in it) for i, it in enumerate(iters)). But also, note that @Jochen is right in the sense that once the first generator in the tuple returned by iunzip_v1 is used up, the remaining generators are no longer really "lazy." As the tee docs say, "This itertool may require significant auxiliary storage."

Jochen Ritzel · Accepted Answer · 2011-06-21 22:58:38Z

5

Ok this is a bit tricky. When you use a name like i the value it stands for is looked up just during runtime. In this code:

return tuple((elem[i] for elem in it) for i, it in enumerate(iters))

you return a number of generators, (elem[i] for elem in it) and each of them uses the same name i. When the function returns, the loop in tuple( .. for i in .. ) has ended and i has been set to it's final value (3 in your example). Once you evaluate these generators to lists, they all create the same values because they are using the same i.

Btw:

unzip = lambda zipped: zip(*zipped)

edited Jun 21, 2011 at 22:58

answered Jun 21, 2011 at 22:52

Jochen Ritzel

108k33 gold badges205 silver badges196 bronze badges

1 Comment

Andrés Moreira Over a year ago

Hi Jochen, thanks for your reply. I left a comment here [stackoverflow.com/questions/6432782/python-nested-generators/… that explain what I've found and my confussion. Thanks again

Collectives™ on Stack Overflow

Python nested generators

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related