The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Java question (quadratic)

We all know that StringBuffer is more efficeint than String for lots of concatenations.  Consider this sentence from a very popular book on Java:

"Using the string concatenation operator repeatedly to concatenate n strings requires time quadratic in n."

Time quadratic?  Quadratic??

The dictionary defines quadratic as "involving terms of the second degree at most".

So, as near as I can figure, because both strings are copied when using the string concatenation operator (+) rather than just one when the StringBuffer.append() class is used, that is the "second degree" of quadratic.

Have I correctly deconstructed the term "quadratic" as it applies to the use in the book?  Tell me, does anybody really use "quadratic" in every day discussions, even among developers?
OneMist8k
Tuesday, March 13, 2007
 
 
Mark Jeffcoat Send private email
Tuesday, March 13, 2007
 
 
The dictionary defines quadratic as "involving terms of the second degree at most".

The Concise Oxford English Dictionary defines it as:

1. involving the second and no higher power of an unknown quantity or variable.  2. Square.


It's a fancy way, as the previous poster said, to say "O(n^2)"
Dan Fleet Send private email
Tuesday, March 13, 2007
 
 
Right.

Constant: O(1)
Logarithmic: O(lg n)
Linear: O(n)
Quadratic: O(n^2)
Exponential: O(c^n)
Factorial: O(n!)

Of those, the only ones you'll hear commonly in conversation are constant and linear. Most people use the big-O notation directly for the rest.
clcr
Tuesday, March 13, 2007
 
 
Shouldn't we be using StringBuilder instead of StringBuffer? At least if you're Java 5 and above?
TownDrunk Send private email
Tuesday, March 13, 2007
 
 
"Shouldn't we be using StringBuilder instead of StringBuffer? At least if you're Java 5 and above?"

If you're single-threaded and care enough about the minor performance difference, I suppose.
Dan Fleet Send private email
Tuesday, March 13, 2007
 
 
"Using the string concatenation operator repeatedly to concatenate n strings requires time quadratic in n."

If you start by concatenating onto an empty string then the first string is copied n times, the second string is copied n-1 times, etc. In total there are (n^2-n)/2, which is "quadratic in n."  Appending into a (sufficiently large) buffer copies each string only once, for a total of n, which is "linear in n."

No, it doesn't come up every day.  But yes, it does get talked about because the choice can make a huge performance difference.  The bigger n, the bigger the difference.  Any time you are doing something nonlinear you should be aware just how nonlinear it is, and consider whether the situation calls for alternatives or mitigations.
Mikkin
Tuesday, March 13, 2007
 
 
If I remember correctly, there was a forum post of blog about how the JVM automatically uses StringBuffer for concatenation of Strings. So while its better to explicitly do it in your code, you generally received the same optimization regardless (and thus could confuse you if you were benchmarking out of curiousity).

Of course, I could be totally wrong. Just something that got stuck in the back my head as sounding plausable and interesting.
Manes
Tuesday, March 13, 2007
 
 
Java does (or can, I suppose its up to the JVM unless its specifically in the spec) use StringBuffer for concats, but there's a gotcha.

Java String objects, once created, cannot be changed.

So when you do

String myStr

...

myStr = myStr + "abc123"


Java has to initialize a StringBuffer with myStr's value, then append "abc123" to it, then convert it back out to a String, and replace myStr's reference with one to the converted String.

That's OK if you do:

myStr = myStr + "foo" + someVar + "bar" + someMethod();


but not if you're doing

while (someVal<SOME_CONST)
{
  myStr = myStr + "abc123";
  ++someVal;
}


or
myStr = myStr + "foo";
myStr = myStr + someVar;
...

i.e. constructing a string in a loop or more than one statement.
Dan Fleet Send private email
Tuesday, March 13, 2007
 
 
StringBuffer worked fine - the program zips through all the appending of strings at the speed of snot.

My happiness is quadratic.
OneMist8k
Tuesday, March 13, 2007
 
 
Constant: O(1)
Logarithmic: O(lg n)
Linear: O(n)
Quadratic: O(n^2)
Exponential: O(c^n)
Factorial: O(n!)

Bah. You left out a couple:

Nihilistic: O(0) --for those uberhackers who never got their careers started.

Bogo: O(n × n!) --Mainly used in the superefficient (for n==1 or n==2) bogosort: http://en.wikipedia.org/wiki/Bogosort
mynameishere Send private email
Wednesday, March 14, 2007
 
 
Consider this paragraph from the StringBuffer Javadoc  http://java.sun.com/j2se/1.4.2/docs/api/java/lang/StringBuffer.html   

Implementation advice: This method can be coded so as to create a new String object without allocating new memory to hold a copy of the character sequence. Instead, the string can share the memory used by the string buffer. Any subsequent operation that alters the content or capacity of the string buffer must then make a copy of the internal buffer at that time. This strategy is effective for reducing the amount of memory allocated by a string concatenation operation when it is implemented using a string buffer.

So I wouldn't automatically assume it's quadratic. The JDK designers seemed to be aware of this issue.
cbmc64 Send private email
Wednesday, March 14, 2007
 
 
Thanks, cb.  I'm building a big ol' StringBuffer using records from a database, so the memory share gambit probably won't work so well.  It loops through records and rows (thus the quadratic element).

One thing I just found out is that the default constructor allocates only 16 bytes, and gets more as needed during overflows.  Changing the initial size at creation will probably get me more speed, even though speed isn't a problem now.

(In my best Tommy Chong voice)  "Quadratic, man!"
OneMist8k
Wednesday, March 14, 2007
 
 
"Changing the initial size at creation will probably get me more speed, even though speed isn't a problem now."

Yes, but probably not as much as you might think. If the implementor of StringBuffer was halfway competent, concatenating into one will be O(log n). The biggest win will come in situations where you know the resulting string length ahead of time and can preallocate a buffer of the right size.
clcr
Wednesday, March 14, 2007
 
 
cbmc64,
I believe this was changed in Java5, since the quoted block was removed. If I recall correctly, this "feature" could cause a memory leak because if you kept a reference to a substring it would maintain the entire StringBuffer as it wasn't fully dereferenced.
Manes
Wednesday, March 14, 2007
 
 
<One thing I just found out is that the default constructor allocates only 16 bytes>

Off topic...maybe you mean 16 characters, which means it's actually more than 16 bytes.
jhanx Send private email
Thursday, March 15, 2007
 
 
Oops - yes, 16 characters. My bad.  But the point is still the same.  The default size size is never large enough.
OneMist8k
Thursday, March 15, 2007
 
 
Just in case not everyone knows of it, there is this constructor.

public StringBuffer(int length);

Which allows the user to set the initial capacity larger where necessary for better performance.
cbmc64 Send private email
Monday, March 19, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz