Speeding up: s += "string"

[Erik Max Francis]

Beat Bolli wrote:

> When I'm really concerned about speed, I pre-bind the append method:
> 
>      lst = []
>      add = lst.append
>      for many times:
>          add(stuff)
>      return ''.join(lst)
> 
> You could also define a global concat function:
> 
>      concat = ''.join
> 
> and use this in the last line above.

The expense here is not in the calling of the function, it's in the time
it takes the function to run.  Repeatedly using

	string += moreData

in a tight loop is expensive because, although the statement looks nice
and clean, strings are immutable and so this is constantly creating and
destroying string objects -- strings which get invariably bigger as the
loop continues.  A loop over this is an O(n^2) operation, which in
computer science parlance "sucks."

As Lulu pointed out, the better solution is to build a list -- because
appending to a list is amortized O(1) -- and then joining the string all
in one go.

-- 
 Erik Max Francis / max at alcyone.com / http://www.alcyone.com/max/
 __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/  \ When angry, count four; when very angry, swear.
\__/ Mark Twain
    Bosskey.net: Quake III Arena / http://www.bosskey.net/q3a/
 A personal guide to Quake III Arena.