[Tutor] python list, right! but concretely?

[Steven D'Aprano]

On Sun, 2 May 2010 07:44:22 pm Lie Ryan wrote:

> Python's 'list' is an array of pointers to `PyObject` ('object' in
> Python) and the resizing algorithm keeps the list size such that
> "allocated / 2 <= actual <= allocated". When list need to resize, it
> overallocates the list slightly over 1.125 times than the requested
> size "(newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize".
>
> If you're interested in more precise details (since I do omit some,
> especially those that seems to be micro-optimization-related), you
> need to read the source at
> http://code.python.org/hg/trunk/file/e9d930f8b8ff/Objects/listobject.c

Thanks for the correction Lie. However, I don't understand what is going 
on in the code. I'm not a C programmer, so I'm struggling to read it, 
but as far as I can tell the comment in the code and the code itself 
are not the same.

The code calculates an amount to over-allocate the list:

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

Some experiments in Python shows that the right hand expression varies 
like this:

>>> for i in range(30):
...     print ((i >> 3) + (3 if i < 9 else 6)),
...
3 3 3 3 3 3 3 3 4 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9


But the comment in the code says:

/* 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, ...
*/

which doesn't look anything like the numbers above. I don't understand 
what this growth pattern refers to. What have I misunderstood?



-- 
Steven D'Aprano