21.11.17 11:44, Serhiy Storchaka пише:
The roundrobin() implementation in recipes has quadratic time for large
number of iterables. As well as all other proposed implementations. This
is a problem if you use it with hundreds or thousands of iterables. For
example:
list(roundrobin(*([[1]]*1000)))
next(roundrobin(*([[]]*1000 + [[1]]])))
The following implementation has linear time.
def roundrobin(*iterables):
"roundrobin('ABC', 'D', 'EF') --> A D E B F C"
nexts = [iter(it).__next__ for it in iterables]
while nexts:
next_nexts = []
append = next_nexts.append
for next in nexts:
try:
yield next()
except StopIteration:
pass
else:
append(next)
nexts = next_nexts
Actually it expands cycle() in Python. And this makes it slower for
smaller number of iterations.
Yet one natural implementation with linear time is:
from collections import deque
def roundrobin(*iterables):
"roundrobin('ABC', 'D', 'EF') --> A D E B F C"
nexts = deque(iter(it).__next__ for it in iterables)
popleft = nexts.popleft
append = nexts.append
while nexts:
next = popleft()
try:
yield next()
except StopIteration:
pass
else:
append(next)
As the previous example it doesn't have any relation to itertools.
_______________________________________________
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/
