469,935 Members | 1,831 Online

# String Concatenation O(n^2) (was: Re: Explaining Implementing aBinary Search Tree.)

Summary: can't verify big O claim, how to properly time this?

On Jun 15, 2:34 pm, "Terry Reedy" <tjre...@udel.eduwrote:
"Bart Kastermans" <bkast...@gmail.comwrote in message

|I wrote a binary search tree in python, explaining as I was doing it
| how and why I did it. I am very interested in receiving comments on
| the code, process, and anything else that will improve my coding or
| writing.
|
| I wrote this all up in my blog at:
|
|http://kasterma.wordpress.com/2008/0...-binary-search...
|
| The code of the class has been copied below, but the description of
| the process (mostly an attempt at approaching test driving development
| for as far as I understand the term) has not been copied.
|
| Any and all comments are appreciated.
|
| Best,
| Bart
|
| *********** python code ************************
|
|
| import re
|
| class BSTree:
| def __init__ (self, value = None):
| self.value = value
| self.left = None
| self.right = None

There are two possible approaches.
1. Define 1 tree class that is also used for subtrees -- what you did.
Complication: self.value of root node can be none, so you constantly
have to check self.value for None even though only possible for root node.
2. Define tree class and node class. This had other complications, but
removes that above and makes str easier. tree.str = '(' str(rootnode) ')'
and node.str= self.value '(' str(self.left) ')' '(' str(self.right) ')'.

If use '' instead of None, no conditionals are needed. (This might apply
partly to your version as well.) Or define class NullTree with a singleton
instance with no attributes and a str method returning '' and an inOrder
method yielding nothing. This would also eliminate the condifionals in the
inOrder method. Not sure what is best. With a good test suite, it is easy
to make sure alternative implementations 'work' before testing for speed.
Thanks for the idea. I would expect the separation to lead to
somewhat more
code, but all the "checking the root" code would be separated out in
the
tree class. The node class would be very smooth. I'll try this when
I have
some time (today I spend my "alloted" programming time on what is
below).

(also the comment about inOrder returning a generator was because I
tried to
figure it out, failed, and then got enough by doing it without yield.
I forgot
to bring my comment in line with my code. A generator
would certainly be nicer, and I'll work at understanding your
suggestion for
it.)
>
| 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.
This is interesting. I had never attempted to verify a big O
statement
before, and decided that it would be worth trying. So I wrote some
code to
collect data, and I can't find that it goes quadratic. I have the
graph
at

http://kasterma.wordpress.com/2008/0...concatenation/

It looks piecewise linear to me.

The code I used to collect the data is as follows:

************************************************** ***********************

import time

NUMBER = 100 # number of strings to concatenate at given length
JUMP = 500 # jump (and start length) of length of strings
END = 100001 # longest length string considered

def randomString (length):
""" returns a random string of letters from {a,b,c,d} of length
"""

string = ""

for i in range (0,length):
string += choice ("abcd")

return string

def randomStrings (number, length):
""" returns an array of number random strings all of length """

array = []

for i in range (0, number):
array.append (randomString (length))

return array

TimingData = []

for length in range (JUMP, END, JUMP):
array1 = randomStrings (NUMBER, length)
array2 = randomStrings (NUMBER, length)

starttime = time.clock ()
for i in range (0, NUMBER):
string = array1 [i] + array2 [i]
endtime = time.clock ()
print "length", length, "done"

TimingData.append ([length, 1000* (endtime-starttime)])
# to get a better looking graph multiply by 1000

sagefile = open ('stringConcatGraph.sage', "w")
sagefile.write ("points =" + str (TimingData) + "\n")
sagefile.write ("graph = line (points)\n")
sagefile.write ("graph.show ()\n")
sagefile.close ()

Jun 27 '08 #1
2 2022
En Mon, 16 Jun 2008 07:34:06 -0300, Bart Kastermans <bk******@gmail.comescribió:
Summary: can't verify big O claim, how to properly time this?

This is interesting. I had never attempted to verify a big O
statement
before, and decided that it would be worth trying. So I wrote some
code to
collect data, and I can't find that it goes quadratic.
In your test code, you're concatenating only two strings, that's a *single* operation, and takes time proportional to the total length.
The quadratic behavior appears when you do *several* concatenations in a row (like in your original code, where += was used several times to build a result).
If you want to verify it, try joining N strings of size M (for varying values of N and M), and plot total time vs. N (for a given M value), and total time vs. M (for a given N value) and finally total time vs. (N*M), see what happens and post your findings again.

--
Gabriel Genellina

Jun 27 '08 #2
On Jun 17, 1:01*am, "Gabriel Genellina" <gagsl-...@yahoo.com.ar>
wrote:
En Mon, 16 Jun 2008 07:34:06 -0300, Bart Kastermans <bkast...@gmail.comescribió:
Summary: can't verify big O claim, how to properly time this?
This is interesting. *I had never attempted to verify a big O
statement
before, and decided that it would be worth trying. *So I wrote some
code to
collect data, and I can't find that it goes quadratic.

In your test code, you're concatenating only two strings, that's a *single* operation, and takes time proportional to the total length.
The quadratic behavior appears when you do *several* concatenations in a row (like in your original code, where += was used several times to build aresult).
If you want to verify it, try joining N strings of size M (for varying values of N and M), and plot total time vs. N (for a given M value), and total time vs. M (for a given N value) and finally total time vs. (N*M), see what happens and post your findings again.

--
Gabriel Genellina
I did the work and found that for trees it does not go quadratic at
all, from the computations you suggest it is easy to get quadratic
behavior though. Also this does not depend in any way I can see on
the implementation by Python. Actual time might certainly improve by
doing it differently (changing the constants), but the big O results
won't.

For pictures and math I have put it up on my blog again see:
http://kasterma.wordpress.com/2008/0...catenation-ii/

Thanks to everyone who commented so far on this subject. I had some
good fun with it so far.

Best,
Bart
Jun 27 '08 #3

### This discussion thread is closed

Replies have been disabled for this discussion.