ExerciseWarm-up
Warm-up
Measure the quadratic curve
5 minfresher0–4 yrs
One concept, guided. Near-impossible to fail.
What this teaches
- Doubling the input doubles a builder's time and quadruples concatenation's
- That ratio is what O(n^2) feels like from the outside
- A single concatenation expression is not the problem
- capacity() and length() answer different questions
Starter
Starter.java
/**
* Warm-up: don't take "quadratic" on faith — watch the ratio.
*
* Absolute milliseconds tell you about your laptop. The RATIO between two input
* sizes tells you about the algorithm, and it is the same on every machine.
*/
public class Starter {
static long ms(Runnable r) {
long start = System.nanoTime();
r.run();
return (System.nanoTime() - start) / 1_000_000;
}
static void sink(boolean b) {
if (!b) System.out.print("");
}
static String byConcatenation(int n) {
String result = "";
for (int i = 0; i < n; i++) result += "x";
return result;
}
static String byBuilder(int n) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append("x");
return sb.toString();
}
public static void main(String[] args) {
// Untimed pass so the JIT has compiled both loops before measuring.
sink(byConcatenation(2_000).length() == 2_000);
sink(byBuilder(2_000).length() == 2_000);
int small = 20_000;
int large = small * 2;
long concatSmall = ms(() -> sink(byConcatenation(small).length() == small));
long concatLarge = ms(() -> sink(byConcatenation(large).length() == large));
long buildSmall = ms(() -> sink(byBuilder(small).length() == small));
long buildLarge = ms(() -> sink(byBuilder(large).length() == large));
System.out.println("n = " + small);
System.out.println(" s += \"x\" " + concatSmall + "ms");
System.out.println(" sb.append(\"x\") " + buildSmall + "ms");
System.out.println("n = " + large + " (double)");
System.out.println(" s += \"x\" " + concatLarge + "ms");
System.out.println(" sb.append(\"x\") " + buildLarge + "ms");
System.out.println();
System.out.println("concatenation ratio = " + ratio(concatSmall, concatLarge) + "x");
System.out.println("builder ratio = " + ratio(buildSmall, buildLarge) + "x");
// TODO 1: doubling the input roughly QUADRUPLED one of them and roughly
// DOUBLED the other. Which is which, and which one is O(n^2)?
// TODO 2: add a third measurement that concatenates ONCE rather than in
// a loop:
// String s = "a" + small + "b" + large + "c";
// Time it. Does it belong in the same conversation as the loop?
// TODO 3: add a builder pre-sized with new StringBuilder(large).
// Compare it to the un-sized builder. Is the difference big enough to
// care about, and where would you actually bother?
// TODO 4: print capacity() and length() after appending 5 characters to
// a fresh StringBuilder. Explain why they differ.
}
static String ratio(long small, long large) {
if (small == 0) return "too fast to measure — raise n";
return String.valueOf(Math.round((double) large / small));
}
}Run it locally:
cd exercises/java/strings/string-vs-stringbuilder/01-warmup
javac Starter.java -d /tmp/out && java -cp /tmp/out StarterDone when
- You ran it at two input sizes and compared the ratios, not the absolute times
- You can say which ratio indicates quadratic behaviour and why
- You pre-sized a builder and can say when that is worth doing
← Back to What is the difference between String, StringBuilder and StringBuffer?