Efficient string concatenation methods

[jtd]

python at rcn.com (Raymond Hettinger) wrote in message news:<5d83790c.0405021752.2b82345e at posting.google.com>...

> API.  The real issue is how much space to allocate for the final
> string.  When iterating, as you do, there is little forewarning about
> how many more entries to expect or the length of each.  If too little
> space is allocated, then room for a larger string needs to be created
> and the previous result recopied (giving the O(n**2) behavior you're
> trying to get rid of).

Is there any particular reason why the space allocated does not
increase *exponentially*, say with a factor of 1.5 or 2? That's how
the string class is implemented in C++, IIRC. That'd give you
amortized linear rather than quadratic time.