List Performance

[Terry Reedy]

Maric Michaud wrote:
> Le Monday 30 June 2008 15:52:56 Gerhard Häring, vous avez écrit :
>> Larry Bates wrote:

>> 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

datas = [None] * expected_size
has been a standard idiom since before object() existed ;-)
and works fine *unless* one wants to add None explicitly
and have that be different from 'unused'.

> 
> # 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.

An interesting idea if one does this at least a few times and wants to 
use .append and .extend instead of explicit indexing.

One could also make such a subclass a 'no-grow' list if appropriate 
(when an attempt to grow it would indicate a bug).

tjr