Re: List Performance

Le Monday 30 June 2008 15:52:56 Gerhard Häring, vous avez écrit :
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

--
http://mail.python.org/mailman/listinfo/python-list

Well, as I posted few days ago, one could envisage, as a pure python
optimization for dealing with long list, to replace an algorithm with a lot
of append by something like this :

mark = object()

datas = [ mark ] * expected_size

# working with the datas while maintaining the effective currrently used size

Of course one could even subclass list and redefine __len__, append, and some
other methods to deal with this "allocated by block" list.


--
_____________

Maric Michaud
.

Relevant Pages

  • 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
    ... So its actually faster to append to a long list than an empty one? ... They overallocate, and the amount of overallocation is dependent on the current size. ... But you can't do it directly from Python, ...
    (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)