Strings are better than lists for the tree to string operation.

Bart Kastermans bkasterm at gmail.com
Mon Jun 30 22:04:09 CEST 2008


> |    def __str__ (self):
>
> string appending is an O(n**2) operations.  The usual idiom, applied here,
> would be slist = ['('], slist.append(str(self.value)), .... return
> ''.join(slist).  In other words, collect list of pieces and join at end.

I did some timing of operations involved.  Doing this I found that
the operation below to get a string representation for trees was
in fact not quadratic.

The final nail in the coffin of this comment is now at:
http://kasterma.wordpress.com/2008/06/30/strings-versus-lists/
(I put it there because the main part is a graph of timing data)

Appending for lists is slower than appending the strings.

This means that the operation using strings is faster.

Again, thanks for all the comments, I enjoyed working this out.  Even
better would be to point out any mistakes in my arguments or code.

Best,
Bart

>
> |        string = "("
> |        if not self.value == None:
> |            string += str (self.value)
> |
> |        if not (self.left == None and self.right == None):
> |            if self.left != None:
> |                string += str (self.left)
> |            else:
> |                string += "()"
> |
> |            if self.right != None:
> |                string += str (self.right)
> |            else:
> |                string += "()"
> |
> |        string += ")"
> |
> |        return string
> |



More information about the Python-list mailing list