[issue20727] Improved roundrobin itertools recipe
New submission from David Lindquist: The roundrobin example in the Recipes section of the itertools documentation (http://docs.python.org/3/library/itertools.html#itertools-recipes) is overly complex. Here is a more straightforward implementation: def roundrobin(*iterables): "roundrobin('ABC', 'D', 'EF') --> A D E B F C" sentinel = object() it = chain.from_iterable(zip_longest(fillvalue=sentinel, *iterables)) return (i for i in it if i is not sentinel) Not only is it one-third the lines of the existing example, benchmarks show it to be more than twice as fast. See attached patch file. ---------- assignee: docs@python components: Documentation files: roundrobin.patch keywords: patch messages: 211907 nosy: david.lindquist, docs@python priority: normal severity: normal status: open title: Improved roundrobin itertools recipe versions: Python 2.7, Python 3.1, Python 3.2, Python 3.3, Python 3.4, Python 3.5 Added file: http://bugs.python.org/file34180/roundrobin.patch _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Changes by Ned Deily <nad@acm.org>: ---------- nosy: +rhettinger _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Changes by Antoine Pitrou <pitrou@free.fr>: ---------- stage: -> patch review versions: -Python 3.1, Python 3.2, Python 3.5 _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Raymond Hettinger added the comment: I like the brevity and clarity of your version. If you would like, I can also add your name as the credit for the recipe. It is up to Larry whether this goes in before or after the 3.4 release. ---------- assignee: docs@python -> rhettinger nosy: +larry priority: normal -> low type: -> performance _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Larry Hastings added the comment: Doc changes are fine basically anytime, but I don't want low-priority changes in Lib for 3.4.0. But this would be fine for 3.4.1 if you like, or you could just wait for 3.5. ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Raymond Hettinger added the comment: It's a doc change only. Do you want it in the 3.4.0RC or in 3.4.1? ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Larry Hastings added the comment: The patch attached to this issue has changes to Lib/test/test_itertools.py. ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Raymond Hettinger added the comment: Okay, after the RC then. David, would you like to be credited in the recipe? ---------- resolution: -> remind _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
David Lindquist added the comment: Sure. That would be nice. :) Thanks Raymond and Larry ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Gareth Rees added the comment:
benchmarks show it to be more than twice as fast
I'm sure they do, but other benchmarks show it to be more than twice as slow. Try something like: iterables = [range(100)] + [()] * 100 ---------- nosy: +Gareth.Rees _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
David Lindquist added the comment:
other benchmarks show it to be more than twice as slow
Can you share the method you used to get those results? Here's what I did: $ python -m timeit --number=1000000 --setup="from rr_mine import roundrobin" "its = ['ABC', 'D', 'EF']; list(roundrobin(*its))" 1000000 loops, best of 3: 6.59 usec per loop $ python -m timeit --number=1000000 --setup="from rr_theirs import roundrobin" "its = ['ABC', 'D', 'EF']; list(roundrobin(*its))" 1000000 loops, best of 3: 14.4 usec per loop Using your recommended iterables (reducing the number of executions so it completes in my lifetime), the results are much closer, but my version still edges out the original: $ python -m timeit --number=10000 --setup="from rr_mine import roundrobin" "its = [range(100)] + [()] * 100; list(roundrobin(*its))" 10000 loops, best of 3: 641 usec per loop $ python -m timeit --number=10000 --setup="from rr_theirs import roundrobin" "its = [range(100)] + [()] * 100; list(roundrobin(*its))" 10000 loops, best of 3: 699 usec per loop ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Gareth Rees added the comment: If 100 doesn't work for you, try a larger number. ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Gareth Rees added the comment: I suspect I messed up the timing I did yesterday, because today I find that 100 isn't large enough, but here's what I found today (in Python 3.3): >>> from timeit import timeit >>> test = [tuple(range(300))] + [()] * 100 >>> timeit(lambda:list(roundrobin1(*test)), number=10000) # old recipe 8.386148632998811 >>> timeit(lambda:list(roundrobin2(*test)), number=10000) # new recipe 16.757110453007044 The new recipe is more than twice as slow as the old in this case, and its performance gets relatively worse as you increase the number 300. I should add that I do recognise that the new recipe is better for nearly all cases (it's simpler as well as faster), but I want to point out an important feature of the old recipe, namely that it discards iterables as they are finished with, giving it worst-case O(n) performance (albeit slow) whereas the new recipe has worst case O(n^2). As we found out with hash tables, worst-case O(n^2) performance can be a problem when inputs are untrusted, so there are use cases where people might legitimately prefer an O(n) solution even if it's a bit slower in common cases. ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Gareth Rees added the comment: But now that I look at the code more carefully, the old recipe also has O(n^2) behaviour, because cycle(islice(nexts, pending)) costs O(n) and is called O(n) times. To have worst-case O(n) behaviour, you'd need something like this: from collections import deque def roundrobin3(*iterables): "roundrobin('ABC', 'D', 'EF') --> A D E B F C" nexts = deque(iter(it).__next__ for it in iterables) while nexts: try: while True: yield nexts[0]() nexts.rotate(-1) except StopIteration: nexts.popleft() >>> from timeit import timeit >>> test = [tuple(range(1000))] + [()] * 1000 >>> timeit(lambda:list(roundrobin1(*test)), number=100) # old recipe 5.184364624001319 >>> timeit(lambda:list(roundrobin2(*test)), number=100) # new recipe 5.139592286024708 >>> timeit(lambda:list(roundrobin3(*test)), number=100) 0.16217014100402594 ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
David Lindquist added the comment: Thanks Gareth for your analysis. Very informative! ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Changes by Chris Rebert <pybugs@rebertia.com>: ---------- nosy: +cvrebert _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue20727> _______________________________________
Raymond Hettinger <raymond.hettinger@gmail.com> added the comment: Thanks for the suggestion. I appreciate it even though I've decided to keep the current recipe. While he proposed recipe is really good at eliminating exhausted input sources, it is slower at its core task of yielding outputs (which is typically the important part). The O(n) step in the current code runs at C speed and is really fast. On my six year old machine, running :cycle(islice(nexts, num_active))" for 1,000 nexts takes only 186ns. One other thought: The existing recipe is also useful for showing off ways to use the itertools (which was really the principal purpose of having a recipes section). ---------- resolution: remind -> rejected stage: patch review -> resolved status: open -> closed _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue20727> _______________________________________
participants (7)
-
Antoine Pitrou -
Chris Rebert
-
David Lindquist
-
Gareth Rees
-
Larry Hastings
-
Ned Deily
-
Raymond Hettinger