Author gdr@garethrees.org
Recipients david.lindquist, docs@python, gdr@garethrees.org, larry, rhettinger
Date 2014-02-25.13:04:14
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1393333455.28.0.523637259087.issue20727@psf.upfronthosting.co.za>
In-reply-to
Content
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
History
Date User Action Args
2014-02-25 13:04:15gdr@garethrees.orgsetrecipients: + gdr@garethrees.org, rhettinger, larry, docs@python, david.lindquist
2014-02-25 13:04:15gdr@garethrees.orgsetmessageid: <1393333455.28.0.523637259087.issue20727@psf.upfronthosting.co.za>
2014-02-25 13:04:15gdr@garethrees.orglinkissue20727 messages
2014-02-25 13:04:14gdr@garethrees.orgcreate