Tim Wintle wrote: > Basically malloc() and free() are computationally expensive, so Python > tries to call them as little as possible - but it's quite clever at > knowing what to do - e.g. if a list has already grown large then python > assumes it might grow large again and keeps hold of a percentage of the > memory.
You are almost right. Python's mutable container types like have a non-linear growth rate. >From the file listobject.c /* 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); -- http://mail.python.org/mailman/listinfo/python-list
