[Python-ideas] Rewriting the "roundrobin" recipe in the itertools documentation
storchaka at gmail.com
Tue Nov 21 05:44:38 EST 2017
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
> next(roundrobin(*([]*1000 + []])))
> 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:
> yield next()
> except StopIteration:
> 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
"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
next = popleft()
As the previous example it doesn't have any relation to itertools.
More information about the Python-ideas