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 <[email protected]>
<http://bugs.python.org/issue20727>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
