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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
