[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):
        table.extend(tup)
    return table


for i in range(0, 100):
    a = time.time()
    filltable(i*1000)
    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>
<https://bugs.pypy.org/issue1599>
________________________________________


More information about the pypy-issue mailing list