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.

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.

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.

It's a doc change only.  Do you want it in the 3.4.0RC or in 3.4.1?

The patch attached to this issue has changes to Lib/test/test_itertools.py.

Okay, after the RC then.

David, would you like to be credited in the recipe?

Sure. That would be nice. :)

Thanks Raymond and Larry

> 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

> 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

If 100 doesn't work for you, try a larger number.

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.

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

Thanks Gareth for your analysis. Very informative!

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).