Speed of string += string

[logistix]

Alan McIntyre <fusion at thuule.pair.com> wrote in message news:<mailman.1050178039.28676.python-list at python.org>...
> Alan McIntyre wrote:
> > Now I'm inclined to do a comparison just for my own curiosity's 
> > sake...maybe I'll be back with graphs in just a bit. :)
> 
> Here's the times required for adding 200k two-character strings to a 
> single string (in steps of 1000 += operations):
> 
> http://norfolkgraphics.com/testing/test.png
> 
> The green line is for Python, red for C++.  It looks kind of O(n)'ish 
> for both of them.
> 
> Each point in the graph corresponds to the time required to perform 1000 
> += operations (the Python version of the code is below).  I dumped the 
> output of the Python and C++ programs to text files and used SciPy to 
> plot them.
> 
> The total run time for the Python version was 194.069 seconds, the C++ 
> std::string version was 157.386 seconds.   I would have done a plain C 
> version but my curiosity ran out and it's too nice outside. ;)
> 
> Full disclosure: The C++ program was compiled with Borland C++ Builder 
> 5, all optimizations turned on; the Python program is just as you see it 
> below, run on Python 2.2.2 (binary install release from python.org). 
> YMMV.  IANAL.
> 
> ----------------------------------------------------------
> import time
> 
> x = []
> t = []
> s = ''
> 
> starttime = time.time()
> 
> for i in range(200):
>      ts = time.time()
>      for j in range(1000):
>          s += 'aa'
> 
>      x.append(i)
>      t.append(time.time()-ts)
                           ^^^

This is wrong.  You should be doing t.append(time.time()-starttime). 
That will show how much more time 1k, 2k, 3k etc operations will take
compared to 1k.

 Right now you're only timing over and over for groups of 1000.  If
this was linear [O(n)], you'd get a flat line on the graph with your
current equation.