[Edu-sig] How to Improve code performance

[Brent Burley]

> Hi,
> I am little obssessed with my own coded after i
> found out it is slow. I am trying to construct a html
> table string from a result that i obtain from
> database.My code segment look like this: assume result
>  holds 2D list.
>  *******  method********************************
>  def f1(item):
>      return "<td>"+str(item)+"</td>"
>  *****************************************
>  ************main program piece***********
>  tab = "<table align='center' border='1'>\n"
>  for x in result:
>     tab = tab + "<tr>"
>     tab = tab + string.join(map(f1,x),"")+"</tr>\n"
>  tab = tab + "</table>"
>  print "Content-type:text/html\n"
>  print tab
>  **********************************************
>  Can anyone improve this code segment? Thanks alot

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).

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, "")

O(n) will always beat O(n*2) for large enough n, even if the individual
operations are slower.


	Brent