In article <5109fe6b$0$11104$c3e8...@news.astraweb.com>, Steven D'Aprano <steve+comp.lang.pyt...@pearwood.info> wrote:
> On Thu, 31 Jan 2013 02:49:31 +1100, Chris Angelico wrote: > > > it's worth > > noting that list appending is not going to be O(N*N), because it's going > > to allow room for expansion. > > This is true for list.append, which is amortized constant time. But it is > not true for list addition, alist + blist, which is O(N**2) and hence > gets really, really slow: > > steve@runes:~$ python -m timeit "L = []" "for i in xrange(1000): L = L + [1]" > 100 loops, best of 3: 3.08 msec per loop > steve@runes:~$ python -m timeit "L = []" "for i in xrange(5000): L = L + [1]" > 10 loops, best of 3: 71 msec per loop > steve@runes:~$ python -m timeit "L = []" "for i in xrange(25000): L = L + [1]" > 10 loops, best of 3: 2.06 sec per loop > > > Notice that as the number of list additions goes up by a factor of 5, > the time taken goes up by a factor of 25. It's not the addition, per-se, that's the problem. It's the creation of a new list each time. If you use +=, it's back to O(n): ~$ python -m timeit "L = []" "for i in xrange(1000): L += [1]" 1000 loops, best of 3: 275 usec per loop ~$ python -m timeit "L = []" "for i in xrange(5000): L += [1]" 1000 loops, best of 3: 1.34 msec per loop ~$ python -m timeit "L = []" "for i in xrange(25000): L += [1]" 100 loops, best of 3: 6.91 msec per loop -- http://mail.python.org/mailman/listinfo/python-list