Re: List Performance

Larry Bates wrote:
[...]
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?

Maybe not intuitively, but if you know how dynamically growing data structures are implemented, it's plausible. They overallocate, and the amount of overallocation is dependent on the current size. Relevant source snippet from Python 2.6:

/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

If, on the other hand, we knew beforehand how big the list will get approximately, we could avoid all these reallocations. No problem with Python's C API:

PyAPI_FUNC(PyObject *) PyList_New(Py_ssize_t size);

But you can't do it directly from Python, unless you (ab)use ctypes.

-- Gerhard

.

Relevant Pages

  • Re: List Performance
    ... So its actually faster to append to a long list than an empty one? ... but if you know how dynamically growing data ... They overallocate, and the ... But you can't do it directly from Python, ...
    (comp.lang.python)
  • Re: Reading a file that is changing and getting the new lines
    ... As the python script is running a user/application ... Is this an independent process, that appends data onto the same file, after the python script has opened it, but while it's still running? ... the other application simultaneously tries to append. ... I suspect the sharing problems aren't going to be portable between operating systems, so you might want to answer the usual "what version of Python, on what OS" question that we seem to have for most new questions. ...
    (comp.lang.python)
  • Re: List Performance
    ... Python's C API: ... But you can't do it directly from Python, ... Of course one could even subclass list and redefine __len__, append, and some other methods to deal with this "allocated by block" list. ... An interesting idea if one does this at least a few times and wants to use .append and .extend instead of explicit indexing. ...
    (comp.lang.python)
  • Re: Most efficient way to "pre-grow" a list?
    ... possible to grow a list in less than Otime without knowing ... Citation? ... Python uses mildly exponential over-allocation, ... that growing a list takes *amortized* Otime per append. ...
    (comp.lang.python)
  • Re: Append a new value to dict
    ... that appending a new key/value to a dict in Python is awfully cumbersome. ... In Python, this is the best code I could come up with for adding a new key, value to a dict ... Since this looks ugly somebody invented the setdefault method: ... When there's no list yet setdefault will create an empty list and append the first value. ...
    (comp.lang.python)