Adding a new function "zip_flat" to itertools (Re: Rewriting the "roundrobin" recipe in the itertools documentation)
Dear all: thank you for your replies and thoughts, most especially Steve and Terry. I am more-or-less new to contributing to Python, so I wasn't sure that the bug tracker was the best way to start -- I was looking for a sanity check and received exactly what I wanted :) Thanks to the feedback here, the bug tracker issue will be much cleaner from the start. Regarding the meta discussion about my OP: yes it was long winded, detailed, pedantic and (to a certain extent) bombastic, but I was imaging the many possible responses to the suggestion (and suggested replacement) the I felt I should explain where I was coming from. Even though there was a lot of disagreement about how I described the current recipe as not very Pythonic, I'm very glad for all the perspectives and lessons I got from reading the ensuing discussions. Now, having had some time to think, I've come up with further thoughts on the topic. In particular, I was going to create a new bug, and wrote several paragraphs on the topic summarizing this thread, and my thoughts. I'll paste those paragraphs here: """ To summarize, I found the current implementation of the "roundrobin" function difficult to understand, and proposed a much simpler solution that, while producing correct results, isn't quite "correct" in the sense that it glosses over a detail before "manually" correcting the detail at the end, and as such is prone to severe inefficiency in extreme cases. There were a smattering of comments from several people indicating that they liked the simpler recipe better, despite its performance drawbacks. Terry Reedy proposed a slightly rewritten version of the current recipe, which implements the correct algorithm (without glossing over and manually correcting the details). Although I have since changed my perceptions of the original, now understanding how it works, the rewritten version from Terry was clearer enough that I was able to understand *it* where I could not previously understand the original. (My newfound understanding of the original is largely derived from making sense of the rewritten version, which properly clued me in to what cycle and islice actually do. Either way, the current recipe can certainly be improved. Although I now find the original and its rewrite to be algorithmically clean and correct (even if the code and inline comments can be improved), the StackOverflow question ( https://stackoverflow.com/questions/3678869/pythonic-way-to-combine-two-list...) that originally got me thinking about the problem demonstrates that the algorithmically clean way is *not* obvious at all to people who aren't very familiar with the itertools module -- which is the large majority of people who use Python (even if that's a very small fraction of the people reading this bug). The second from top answer is the answer which references the recipe in the docs, but as my own first post to python-ideas demonstrates, the (large?) majority of python users aren't familiar enough with the itertools module to be able to understand that recipe, and I also believe many people were looking for one or two liners to use in their own code without a function call. Further confusion on the overall topic is the lack of a clear name -- "roundrobin", "alternate", "interleave", "merge", and variations and others. """ Having completed those, I found a roughly duplicate StackOverflow question to the one from my OP: https://stackoverflow.com/questions/243865/how-do-i-merge-two-python-iterato... Besides emphasizing my points about not having even a clear name for the topic, a desire for one liners, mass confusion around the issue (especially regarding flattening zip [which terminates on the shortest input, a hidden gotcha], zip_longest [someone else found the same solution as me and others in this op), and all around failure to generate anything even resembling a consensus on the topic, I also found this answer: https://stackoverflow.com/questions/243865/how-do-i-merge-two-python-iterato... which proposes a solution that is both more correct and efficient than the zip_longest-with-sentinels, and also noticeably more readable than either the original doc recipe or even Terry's cleaned up replacement of it. Given this variety of problems with the issue, I now think that -- while updating the itertools recipe is certainly better than nothing -- the better thing to do might be to just add a new function to itertools called "zip_flat" which solves this problem. In addition to answering the stack overflow questions with ongoing debate about efficiency, correctness, and pythonicity (pythonicness?), it would also help to greatly clarify the naming issue as well. (Sidenote: whoever came up with "zip" as the name for the builtin was quite creative. It's a remarkably short and descriptive.) What are the sentiments of readers here? If positive, I'll create an issue on BPO about zip_flat (rather than just improving the docs recipe). (Sorry Steve for bringing this back to -ideas! At least this time I'm proposing an addition to the language itself! :) Thanks for your consideration, Bill On Thu, Nov 16, 2017 at 5:06 PM, Steven D'Aprano <steve@pearwood.info> wrote:
Hi Bill, I don't have time to go through your email in detail and respond to every point you raise, but I'd like to respond to one point you made. On Mon, Nov 20, 2017 at 02:03:13AM -0600, bunslow wrote:
Please don't make claims about correctness and efficiency without testing the code first. The second suggestion given there, using deque, is *not* correct as provided, as it fails to work with iterables. It requires the caller to pass only iterators, unlike the existing roundrobin recipe which accepts any iterable. Nor is it more efficient, at least on my machine -- in fact the opposite, it is the worst performing of the four recipes I've tried: - the current recipe from the itertools docs; - your re-write, using zip_longest; - Terry's version; - and the one from stackoverflow. I've attached my test code, in case you want to play around with it. Apologies in advance for any bugs in the test code (its 2 in the morning here and I've had a long day). According to my testing, on my computer using Python 3.5, Terry's code is by far the fastest in all three separate test cases, but that probably shouldn't count since it's buggy (it truncates the results and bails out early under some circumstances). Out of the implementations that don't truncate, the existing recipe is by far the fastest. Terry, if you're reading this, try: list(roundrobin('A', 'B', 'CDE')) Your version truncates the results to A B C instead of A B C D E as the itertools recipe gives. But I digress... the point is, if you're going to make claims about the correctness and efficiency of code, you really ought to actually check the correctness and efficiency first. I may or may not get around to responding to some of your other points over the next few days. -- Steve
Oops, a slight buglet in my test code: [Attachment: rr_tester.py] Change the constant NUMBER = 30 to the largest value you can bear for more reliable timing tests. I lowered the value for a quick test and forgot to increase it again. -- Steve
On 11/20/2017 11:08 AM, Steven D'Aprano wrote:
Your version truncates the results to A B C instead of A B C D E as the itertools recipe gives.
This is due to an off-by-1 error which I corrected 3 hours later in a follow-up post, repeated below. --- Correct off-by-one error. I should have tested with an edge case such as print(list(roundrobin('ABC', '')))
Make that 0 rather than 1 for start value.
A slightly clearer, slightly less efficient alternative would be def roundrobin(*iterables): "roundrobin('ABC', 'D', 'EF') --> A D E B F C" nexts = cycle(iter(it).__next__ for it in iterables) for current_len in reversed(range(1, len(iterables)+1)): try: for next in nexts: yield next() except StopIteration: nexts = cycle(islice(nexts, current_len - 1)) -- Terry Jan Reedy
After correcting Terry's off-by-one error, I get this on Python 3.6 (and bumping NUMBER to 1000). In speed, Terry's is either very slightly faster or very slightly slower than the recipe, depending on the data. I think Terry's is more readable that roundrobin(), but still requires a little thought compared to Bunslow's. However, using the builtin name 'next' as a variable name seems like a bad choice to me (it doesn't break in this code, but seems like bad practice, i'd choose some other variable name). 507-code % python rr_tester.py testing with equal_data roundrobin 0.187816 bunslow 0.393162 terry 0.183851 stackoverflow 0.675543 ************************************************** testing with unequal_data roundrobin 0.209959 bunslow 0.555731 terry 0.233015 stackoverflow 0.746880 ************************************************** testing with extreme_data roundrobin 0.053149 bunslow 0.273607 terry 0.051963 stackoverflow 0.158515 508-code % python --version Python 3.6.2 :: Anaconda custom (x86_64) On Mon, Nov 20, 2017 at 9:15 AM, Terry Reedy <tjreedy@udel.edu> wrote:
-- Keeping medicines from the bloodstreams of the sick; food from the bellies of the hungry; books from the hands of the uneducated; technology from the underdeveloped; and putting advocates of freedom in prisons. Intellectual property is to the 21st century what the slave trade was to the 16th.
(Regarding the stackoverflow link, he does have a version that includes the trivial fix to apply iter() to args, at the bottom of the post.) I think that the variety of solutions with a variety of merits is indicative that it would be useful to have a "zip_flat" in the itertools module, but I guess support for that isn't very strong here. I see that Terry opened a bug to clean up the current recipe in the docs, which is better than nothing, but I think it's the absolute bare minimum improvement. I'm prepared to drop the subject unless there's further discussion in favor of it. Thanks again to all for the replies. Bill On Mon, Nov 20, 2017 at 10:08 AM, Steven D'Aprano <steve@pearwood.info> wrote:
Hi Bill, I don't have time to go through your email in detail and respond to every point you raise, but I'd like to respond to one point you made. On Mon, Nov 20, 2017 at 02:03:13AM -0600, bunslow wrote:
Please don't make claims about correctness and efficiency without testing the code first. The second suggestion given there, using deque, is *not* correct as provided, as it fails to work with iterables. It requires the caller to pass only iterators, unlike the existing roundrobin recipe which accepts any iterable. Nor is it more efficient, at least on my machine -- in fact the opposite, it is the worst performing of the four recipes I've tried: - the current recipe from the itertools docs; - your re-write, using zip_longest; - Terry's version; - and the one from stackoverflow. I've attached my test code, in case you want to play around with it. Apologies in advance for any bugs in the test code (its 2 in the morning here and I've had a long day). According to my testing, on my computer using Python 3.5, Terry's code is by far the fastest in all three separate test cases, but that probably shouldn't count since it's buggy (it truncates the results and bails out early under some circumstances). Out of the implementations that don't truncate, the existing recipe is by far the fastest. Terry, if you're reading this, try: list(roundrobin('A', 'B', 'CDE')) Your version truncates the results to A B C instead of A B C D E as the itertools recipe gives. But I digress... the point is, if you're going to make claims about the correctness and efficiency of code, you really ought to actually check the correctness and efficiency first. I may or may not get around to responding to some of your other points over the next few days. -- Steve
Oops, a slight buglet in my test code: [Attachment: rr_tester.py] Change the constant NUMBER = 30 to the largest value you can bear for more reliable timing tests. I lowered the value for a quick test and forgot to increase it again. -- Steve
On 11/20/2017 11:08 AM, Steven D'Aprano wrote:
Your version truncates the results to A B C instead of A B C D E as the itertools recipe gives.
This is due to an off-by-1 error which I corrected 3 hours later in a follow-up post, repeated below. --- Correct off-by-one error. I should have tested with an edge case such as print(list(roundrobin('ABC', '')))
Make that 0 rather than 1 for start value.
A slightly clearer, slightly less efficient alternative would be def roundrobin(*iterables): "roundrobin('ABC', 'D', 'EF') --> A D E B F C" nexts = cycle(iter(it).__next__ for it in iterables) for current_len in reversed(range(1, len(iterables)+1)): try: for next in nexts: yield next() except StopIteration: nexts = cycle(islice(nexts, current_len - 1)) -- Terry Jan Reedy
After correcting Terry's off-by-one error, I get this on Python 3.6 (and bumping NUMBER to 1000). In speed, Terry's is either very slightly faster or very slightly slower than the recipe, depending on the data. I think Terry's is more readable that roundrobin(), but still requires a little thought compared to Bunslow's. However, using the builtin name 'next' as a variable name seems like a bad choice to me (it doesn't break in this code, but seems like bad practice, i'd choose some other variable name). 507-code % python rr_tester.py testing with equal_data roundrobin 0.187816 bunslow 0.393162 terry 0.183851 stackoverflow 0.675543 ************************************************** testing with unequal_data roundrobin 0.209959 bunslow 0.555731 terry 0.233015 stackoverflow 0.746880 ************************************************** testing with extreme_data roundrobin 0.053149 bunslow 0.273607 terry 0.051963 stackoverflow 0.158515 508-code % python --version Python 3.6.2 :: Anaconda custom (x86_64) On Mon, Nov 20, 2017 at 9:15 AM, Terry Reedy <tjreedy@udel.edu> wrote:
-- Keeping medicines from the bloodstreams of the sick; food from the bellies of the hungry; books from the hands of the uneducated; technology from the underdeveloped; and putting advocates of freedom in prisons. Intellectual property is to the 21st century what the slave trade was to the 16th.
(Regarding the stackoverflow link, he does have a version that includes the trivial fix to apply iter() to args, at the bottom of the post.) I think that the variety of solutions with a variety of merits is indicative that it would be useful to have a "zip_flat" in the itertools module, but I guess support for that isn't very strong here. I see that Terry opened a bug to clean up the current recipe in the docs, which is better than nothing, but I think it's the absolute bare minimum improvement. I'm prepared to drop the subject unless there's further discussion in favor of it. Thanks again to all for the replies. Bill On Mon, Nov 20, 2017 at 10:08 AM, Steven D'Aprano <steve@pearwood.info> wrote:
participants (5)
-
bunslow -
David Mertz -
Serhiy Storchaka -
Steven D'Aprano -
Terry Reedy