<div>On 12 December 2012 07:52, Ross Ridge <span dir="ltr"><<a href="mailto:rridge@csclub.uwaterloo.ca" target="_blank">rridge@csclub.uwaterloo.ca</a>></span> wrote:<br></div><div class="gmail_extra"><div class="gmail_quote">

<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div>John Gordon wrote:<br>
> def encode(plain):<br>
>     '''Return a substituted version of the plain text.'''<br>
>     encoded = ''<br>
>     for ch in plain:<br>
>        encoded += key[alpha.index(ch)]<br>
>     return encoded<br>
<br>
</div><div>Terry Reedy  <<a href="mailto:tjreedy@udel.edu" target="_blank">tjreedy@udel.edu</a>> wrote:<br>
>The turns an O(n) problem into a slow O(n*n) solution. Much better to<br>
>build a list of chars and then join them.<br>
<br>
</div>There have been much better suggestions in this thread, but John Gordon's<br>
code above is faster than the equivilent list and join implementation<br>
with Python 2.6 and Python 3.1 (the newest versions I have handy).<br>
CPython optimized this case of string concatenation into O(n) back in<br>
Python 2.4.<br></blockquote><div><br></div><div>From "What's New in Python 2.4":</div><div><a href="http://docs.python.org/release/2.4.4/whatsnew/node12.html#SECTION0001210000000000000000" target="_blank">http://docs.python.org/release/2.4.4/whatsnew/node12.html#SECTION0001210000000000000000</a><br>
</div><div><br></div><div>String concatenations in statements of the form s = s + "abc" and s += "abc" are now performed more efficiently <b>in certain circumstances</b>. This optimization <b>won't be present in other Python implementations such as Jython</b>, so you shouldn't rely on it; using the join() method of strings is still recommended when you want to efficiently glue a large number of strings together. <br>
</div><div><br></div><div>Emphasis mine.</div><div><br></div><div>The optimisation was added to improve the situation for programs that were already using the anti-pattern of string concatenation, not to encourage people to use it.</div>
<div><br></div><div>As a real-world case, a bug was recently found in Mercurial where an operation on Windows was taking orders of magnitudes longer than on Linux due to use of string concatenation rather than the join idiom (from ~12 seconds spent on string concatenation to effectively zero).</div>
<div><br></div><div>Tim Delaney</div><div> </div></div></div>