Possible memory leak?

Steven D'Aprano steve at REMOVETHIScyber.com.au
Wed Jan 25 22:00:28 EST 2006

On Wed, 25 Jan 2006 23:20:08 +0000, Giovanni Bajo wrote:

> Of course. I was just trying to make a point about string accumulation being
> O(n) and not O(n^2). 

But according to Fredrik, string accumulation is still quadratic, even
with the optimizations added to Python 2.4. Quoting:

"it only means that if the interpreter can make sure that else is
using the target string, it's modified in place.

however, the string type doesn't use overallocation (beyond the
8-byte alignment provided by the memory allocator), so this fix
only avoids extra copying in a few specific cases.  O(n*n/8) is
still quadratic..."

I presume Fredrik meant to say "nothing else".

Or have I misunderstood something?


More information about the Python-list mailing list