[pypy-issue] [issue1599] quadratic time in list.extend(sometuple)

Antonio Cuni tracker at bugs.pypy.org
Wed Sep 11 19:10:43 CEST 2013

New submission from Antonio Cuni <anto.cuni at gmail.com>:

The functions filltable in the following snippet takes O(N**2) to complete, as
shown by the example. If we turn tup into a list, it takes O(N).

import time

def filltable(N):
    table = []
    tup = (1, 2, 'foo')
    for i in range(N):
    return table

for i in range(0, 100):
    a = time.time()
    b = time.time()
    print '%4d %.2f' % (i, b-a)

messages: 6144
nosy: pypy-issue
priority: performance bug
status: unread
title: quadratic time in list.extend(sometuple)

PyPy bug tracker <tracker at bugs.pypy.org>

More information about the pypy-issue mailing list