[issue20727] Improved roundrobin itertools recipe

[Raymond Hettinger]

Raymond Hettinger  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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Chris Rebert]

Changes by Chris Rebert pyb...@rebertia.com:


--
nosy: +cvrebert

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Gareth Rees]

Gareth Rees added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Gareth Rees]

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=1) # old recipe
8.386148632998811
 timeit(lambda:list(roundrobin2(*test)), number=1) # 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 rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Gareth Rees]

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 rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[David Lindquist]

David Lindquist added the comment:

Thanks Gareth for your analysis. Very informative!

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Raymond Hettinger]

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 rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Larry Hastings]

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 rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Raymond Hettinger]

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 rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Larry Hastings]

Larry Hastings added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Raymond Hettinger]

Raymond Hettinger added the comment:

Okay, after the RC then.

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

--
resolution:  - remind

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[David Lindquist]

David Lindquist added the comment:

Sure. That would be nice. :)

Thanks Raymond and Larry

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Gareth Rees]

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 rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[David Lindquist]

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=100 --setup=from rr_mine import roundrobin 
its = ['ABC', 'D', 'EF']; list(roundrobin(*its))
100 loops, best of 3: 6.59 usec per loop
$ python -m timeit --number=100 --setup=from rr_theirs import roundrobin 
its = ['ABC', 'D', 'EF']; list(roundrobin(*its))
100 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=1 --setup=from rr_mine import roundrobin its 
= [range(100)] + [()] * 100; list(roundrobin(*its))
1 loops, best of 3: 641 usec per loop
$ python -m timeit --number=1 --setup=from rr_theirs import roundrobin 
its = [range(100)] + [()] * 100; list(roundrobin(*its))
1 loops, best of 3: 699 usec per loop

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Ned Deily]

Changes by Ned Deily n...@acm.org:


--
nosy: +rhettinger

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[Antoine Pitrou]

Changes by Antoine Pitrou pit...@free.fr:


--
stage:  - patch review
versions:  -Python 3.1, Python 3.2, Python 3.5

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue20727] Improved roundrobin itertools recipe

[David Lindquist]

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 rep...@bugs.python.org
http://bugs.python.org/issue20727
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com