New submission from Antonio Cuni <[email protected]>:
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 <[email protected]>
<https://bugs.pypy.org/issue1599>
________________________________________
_______________________________________________
pypy-issue mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-issue
