[Python-ideas] Rewriting the "roundrobin" recipe in the itertools documentation

[Serhiy Storchaka]

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.