classification
Title: Improved roundrobin itertools recipe
Type: performance Stage: resolved
Components: Documentation Versions: Python 3.3, Python 3.4, Python 2.7
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: cvrebert, david.lindquist, docs@python, gdr@garethrees.org, larry, rhettinger
Priority: low Keywords: patch

Created on 2014-02-22 06:36 by david.lindquist, last changed 2019-08-22 10:05 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
roundrobin.patch david.lindquist, 2014-02-22 06:36 review
Messages (14)
msg211907 - (view) Author: David Lindquist (david.lindquist) * Date: 2014-02-22 06:36
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.
msg212102 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-02-24 14:36
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.
msg212116 - (view) Author: Larry Hastings (larry) * (Python committer) Date: 2014-02-24 17:22
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.
msg212118 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-02-24 17:27
It's a doc change only.  Do you want it in the 3.4.0RC or in 3.4.1?
msg212120 - (view) Author: Larry Hastings (larry) * (Python committer) Date: 2014-02-24 17:29
The patch attached to this issue has changes to Lib/test/test_itertools.py.
msg212139 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-02-24 20:50
Okay, after the RC then.

David, would you like to be credited in the recipe?
msg212141 - (view) Author: David Lindquist (david.lindquist) * Date: 2014-02-24 21:06
Sure. That would be nice. :)

Thanks Raymond and Larry
msg212153 - (view) Author: Gareth Rees (gdr@garethrees.org) * (Python triager) Date: 2014-02-25 00:45
> 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
msg212161 - (view) Author: David Lindquist (david.lindquist) * Date: 2014-02-25 05:16
> 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
msg212169 - (view) Author: Gareth Rees (gdr@garethrees.org) * (Python triager) Date: 2014-02-25 10:30
If 100 doesn't work for you, try a larger number.
msg212170 - (view) Author: Gareth Rees (gdr@garethrees.org) * (Python triager) Date: 2014-02-25 10:55
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.
msg212174 - (view) Author: Gareth Rees (gdr@garethrees.org) * (Python triager) Date: 2014-02-25 13:04
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
msg212182 - (view) Author: David Lindquist (david.lindquist) * Date: 2014-02-25 15:05
Thanks Gareth for your analysis. Very informative!
msg350179 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-08-22 10:05
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).
History
Date User Action Args
2019-08-22 10:05:04rhettingersetstatus: open -> closed
resolution: remind -> rejected
messages: + msg350179

stage: patch review -> resolved
2014-02-28 17:18:01cvrebertsetnosy: + cvrebert
2014-02-25 15:05:13david.lindquistsetmessages: + msg212182
2014-02-25 13:04:15gdr@garethrees.orgsetmessages: + msg212174
2014-02-25 10:55:04gdr@garethrees.orgsetmessages: + msg212170
2014-02-25 10:30:57gdr@garethrees.orgsetmessages: + msg212169
2014-02-25 05:16:51david.lindquistsetmessages: + msg212161
2014-02-25 00:45:53gdr@garethrees.orgsetnosy: + gdr@garethrees.org
messages: + msg212153
2014-02-24 21:06:09david.lindquistsetmessages: + msg212141
2014-02-24 20:50:17rhettingersetresolution: remind
messages: + msg212139
2014-02-24 17:29:10larrysetmessages: + msg212120
2014-02-24 17:27:56rhettingersetmessages: + msg212118
2014-02-24 17:22:00larrysetmessages: + msg212116
2014-02-24 14:36:31rhettingersetpriority: normal -> low

nosy: + larry
messages: + msg212102

assignee: docs@python -> rhettinger
type: performance
2014-02-22 10:13:54pitrousetstage: patch review
versions: - Python 3.1, Python 3.2, Python 3.5
2014-02-22 09:51:13ned.deilysetnosy: + rhettinger
2014-02-22 06:36:58david.lindquistcreate