classification
Title: itertools.product reference implementation creates temporaries
Type: enhancement Stage: resolved
Components: Documentation Versions: Python 3.11, Python 3.10, Python 3.9
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: AlexWaygood, docs@python, mwallerb, rhettinger
Priority: normal Keywords: patch

Created on 2022-01-14 17:41 by mwallerb, last changed 2022-01-14 22:58 by mwallerb. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 30605 closed mwallerb, 2022-01-14 17:42
Messages (5)
msg410573 - (view) Author: Markus Wallerberger (mwallerb) * Date: 2022-01-14 17:41
The reference implementation of itertools.product creates large temporaries, which we need to remind people of at the top of the code block.

However, using generator magic, we don't need to do this and can even simplify the code in the process!  Basically,we iterate over a generator of product(*seq[:-1]), and extend each of the values by every value in seq[-1].
msg410575 - (view) Author: Alex Waygood (AlexWaygood) * (Python triager) Date: 2022-01-14 17:47
(I'm removing 3.6 and 3.7 from the "versions" field, since those two branches are now only accepting patches if it relates to security.)
msg410598 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2022-01-14 20:30
Markus, thank you for the suggestion but I'm going to decline.  When this rough equivalent was first created, we looked at several recipes and chose this one as being one of the least magical.  Intentionally, we did not use the variant you've proposed.  To a person well versed in recursion and in generator chains it makes sense but not so much for anyone else.  Plus it is hard to step through by hand to see what it is doing.

In general, the rough equivalents were intended to a way to understand what output is going to be generated.  That is why they are mostly simple rather than being faithful to the actual implementations (otherwise, we would use classes rather than generators for all the equivalents).  Viewed in this light, we place almost zero weight to making the recipe memory efficient with respect to temporary variables.
msg410599 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2022-01-14 20:33
Please do keep looking for improvements.  Suggestions are always welcome.
msg410607 - (view) Author: Markus Wallerberger (mwallerb) * Date: 2022-01-14 22:58
> To a person well versed in recursion and in generator chains it makes sense but not so much for anyone else.

There I pretty much fundamentally disagree.  I find the version in the docs much more magical in the sense that it builds up "laterally", i.e., level-by-level, rather than element-by-element.

Also, I think from a functional programming perspective, which, let's face it, is what these iteration/generator tools are really modelling, a recursive version is much more natural.  It also generalizes nicely to other problems which people may be having -- so it has the added benefit of explaining the code and teaching people useful patterns.

Take the itertools.permutation as an example:  writing that as it was in the reference implementation the code is IMHO pretty opaque and hard to reason about.  Write it in a recursive style and both its working and correctness is immediately obvious.

>  Plus it is hard to step through by hand to see what it is doing.

This I agree with.

Anyway, thanks for taking the time to explain the rejection.
History
Date User Action Args
2022-01-14 22:58:52mwallerbsetmessages: + msg410607
2022-01-14 20:33:55rhettingersetmessages: + msg410599
2022-01-14 20:30:01rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg410598

stage: patch review -> resolved
2022-01-14 20:16:14rhettingersetassignee: docs@python -> rhettinger
2022-01-14 17:47:15AlexWaygoodsetnosy: + rhettinger, AlexWaygood

messages: + msg410575
versions: - Python 3.7, Python 3.8
2022-01-14 17:42:26mwallerbsetkeywords: + patch
stage: patch review
pull_requests: + pull_request28804
2022-01-14 17:41:54mwallerbcreate