Re: List Performance

Le Monday 30 June 2008 15:13:30 Larry Bates, vous avez écrit :
Peter Otten wrote:
Ampedesign wrote:
If I happen to have a list that contains over 50,000 items, will the
size of the list severely impact the performance of appending to the
list?

No.

$ python -m timeit -n20000 -s"items = []" "items.append(42)"
20000 loops, best of 3: 0.554 usec per loop
$ python -m timeit -n20000 -s"items = [42]*10**6" "items.append(42)"
20000 loops, best of 3: 0.529 usec per loop

http://wiki.python.org/moin/TimeComplexity

Peter

Peter,

So its actually faster to append to a long list than an empty one? That
certainly would not have been intuitively obvious now would it?


That test only demonstrates that it's faster to append to a 1 million items
list than an empty one (and this on a particular platform with a particular
python version). Different sizes may give different result. I guess this is
because of some internal optimisations (items are probably allocated by
chunks, so sometimes append() involves a realloc, sometimes not).

So the only thing you should remember is that list.append() has a complexity
of O(1), and thus should be considered a constant time operation for any
length. Just be aware of the note:

[1] = These operations rely on the "Amortized" part of "Amortized Worst Case".
Individual actions may take surprisingly long, depending on the history of
the container.

Also note that 50000 items is a lot for a human being, not for a modern
computer.

--
Cédric Lucantis
.

Relevant Pages

  • Re: String concatenation performance with +=
    ... append if and only if there are no other references to the string. ... 1000000 loops, best of 3: 0.231 usec per loop ...
    (comp.lang.python)
  • Re: which is more pythonic/faster append or +=[]
    ... so which is more pythonic/faster? ... ..append - easy to measure, ... 1000000 loops, best of 3: 1.31 usec per loop ...
    (comp.lang.python)
  • Re: reading file
    ... read them in any specific way, for my purpose is solely to append it ... Is it possible to do it, without using any loops or ... just open the file to be append as "append" and write content to it. ... If you don't limit the realization to Fortarn, the command "copy" is ...
    (comp.lang.fortran)
  • Re: reduce()--what is it good for? (was: Re: reduce() anomaly?)
    ... 1000 loops, best of 3: 290 usec per loop ... is about 3 times faster on a typical long seq ... > def longest: ...
    (comp.lang.python)
  • Re: in place input
    ... Python may do lots of allocations and deallocations for ... 1000000 loops, best of 3: 1.16 usec per loop ... creating a 220-character string by using the '*' operator takes just ...
    (comp.lang.python)