469,352 Members | 2,054 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,352 developers. It's quick & easy.

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

On Mon, 16 Jun 2008 10:41:05 -0600, Ian Kelly <ia*********@gmail.comwrote:
>On Mon, Jun 16, 2008 at 4:34 AM, Bart Kastermans <bk******@gmail.comwrote:
>This is interesting. I had never attempted to verify a big O
statement
before, and decided that it would be worth trying. So I wrote some
code to
collect data, and I can't find that it goes quadratic. I have the
graph
at

http://kasterma.wordpress.com/2008/0...concatenation/

It looks piecewise linear to me.

I don't think there's any question that it's quadratic. Just look at
the C code, and you'll see that every time you concatenate the entire
string has to be copied.
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.

Jean-Paul
Jun 27 '08 #1
0 953

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by Jerry Khoo | last post: by
6 posts views Thread by M B HONG 20 | last post: by
32 posts views Thread by tshad | last post: by
34 posts views Thread by Larry Hastings | last post: by
232 posts views Thread by robert maas, see http://tinyurl.com/uh3t | last post: by
5 posts views Thread by nandor.sieben | last post: by
9 posts views Thread by Adriano | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by zhoujie | last post: by
reply views Thread by suresh191 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.