Improved roundrobin itertools recipe

[davidlindquist]

BPO	20727
Nosy	@rhettinger, @larryhastings, @gareth-rees
Files	roundrobin.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2019-08-22.10:05:04.697>
created_at = <Date 2014-02-22.06:36:57.974>
labels = ['docs', 'performance']
title = 'Improved roundrobin itertools recipe'
updated_at = <Date 2019-08-22.10:05:04.695>
user = 'https://bugs.python.org/davidlindquist'

bugs.python.org fields:

activity = <Date 2019-08-22.10:05:04.695>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2019-08-22.10:05:04.697>
closer = 'rhettinger'
components = ['Documentation']
creation = <Date 2014-02-22.06:36:57.974>
creator = 'david.lindquist'
dependencies = []
files = ['34180']
hgrepos = []
issue_num = 20727
keywords = ['patch']
message_count = 14.0
messages = ['211907', '212102', '212116', '212118', '212120', '212139', '212141', '212153', '212161', '212169', '212170', '212174', '212182', '350179']
nosy_count = 6.0
nosy_names = ['rhettinger', 'larry', 'cvrebert', 'docs@python', 'gdr@garethrees.org', 'david.lindquist']
pr_nums = []
priority = 'low'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue20727'
versions = ['Python 2.7', 'Python 3.3', 'Python 3.4']

[davidlindquist]

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.

[rhettinger]

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.

[larryhastings]

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.

[rhettinger]

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

[larryhastings]

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

[rhettinger]

Okay, after the RC then.

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

[davidlindquist]

Sure. That would be nice. :)

Thanks Raymond and Larry

[gareth-rees]

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

[davidlindquist]

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

[gareth-rees]

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