String Concatenation O(n^2) (was: Re: Explaining Implementing a Binary Search Tree.)

Ian Kelly ian.g.kelly at gmail.com
Mon Jun 16 19:30:19 CEST 2008


On Mon, Jun 16, 2008 at 11:09 AM, Jean-Paul Calderone
<exarkun at divmod.com> wrote:
> It will depend what version of Python you're using and the *exact* details
> of the code in question.  An optimization was introduced where, if the
> string being concatenated to is not referred to anywhere else, it will be
> re-sized in place.  This means you'll probably see sub-quadratic behavior,
> but only with a version of Python where this optimization exists and only
> if the code can manage to trigger it.

AFAICT, PyString_Concat never calls _PyString_Resize.  Am I looking in
the wrong place?

-Ian



More information about the Python-list mailing list