469,645 Members | 1,424 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,645 developers. It's quick & easy.

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

| * *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/0...-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
|
Jun 30 '08 #1
0 847

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

17 posts views Thread by Gordon Airport | last post: by
9 posts views Thread by Klaus Neuner | last post: by
15 posts views Thread by Ron Adam | last post: by
10 posts views Thread by Nick Z. | last post: by
89 posts views Thread by scroopy | last post: by
19 posts views Thread by pkirk25 | last post: by
28 posts views Thread by hlubenow | last post: by
2 posts views Thread by bearophileHUGS | last post: by
reply views Thread by gheharukoh7 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.