[Edu-sig] How to Improve code performance

[Martijn Faassen]

Brent Burley wrote:
[snip]
> The big problem is that tab=tab+"..." in a loop is expensive since
> Python must allocate a new string and copy the old one each time.  The
> running time will increase with the square of the number of records,
> i.e. O(n*n).
> 
> It may not be intuitive, but putting all the partial strings in a list
> and then joining them at the end is more efficient as the running time
> will increase only linearly with the number of records, i.e. O(n).

An alternative is to use StringIO (or cStringIO if you're not dealing
with unicode strings):

> tab = []
> tab.append("<table align='center' border='1'>\n")
> for x in result:
>   tab.append("<tr>")
>   for y in x:
>     tab.extend(("<td>",y,"</td>\n"))
>   tab.append("</tr>")
> tab.append("</table>")
> print string.join(tab, "")

from StringIO import StringIO # from cStringIO import StringIO

result = StringIO()
result.write('<table align="center" border="1">\n')
for x in result:
    result.write("<tr>")
    for y in x:
        result.write("<td>")
        result.write(y)
        result.write("</td>\n")
    result.write("</tr>")
result.write("</table>")
print result.getvalue()

For an extra speedboost you could do this on top:

write = result.write

and then you can just use:

write("<tr">)

and so on.

I believe cStringIO can be even faster than the .join() operation,
but I haven't timed it.

Regards,

Martijn