[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 <report at bugs.python.org>
<http://bugs.python.org/issue20727>
_______________________________________