Warm-up

Measure the quadratic curve

5 minfresher04 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 Starter

Done 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?