CSC300 / CSC402: XPerformanceOfStrings [13/13]

Note: Java's StringBuilder can be used instead of StringBuffer.

  public static String makeStringUsingBuffer (int N) {
    StringBuffer result = new StringBuffer ();
    for (int i=0; i<N; i+=1) { 
      result.append ("*");
    }
    return result.toString ();
  }

Output

********************************
Elapsed count f(          512):               512:      2.000 [     0.001 :   Infinity]
Elapsed count f(        1,024):             1,024:      2.000 [     0.000 :      0.000]
Elapsed count f(        2,048):             2,048:      2.000 [     0.000 :        NaN]
Elapsed count f(        4,096):             4,096:      2.000 [     0.000 :        NaN]
Elapsed count f(        8,192):             8,192:      2.000 [     0.001 :   Infinity]
Elapsed count f(       16,384):            16,384:      2.000 [     0.002 :      2.000]
Elapsed count f(       32,768):            32,768:      2.000 [     0.002 :      1.000]
Elapsed count f(       65,536):            65,536:      2.000 [     0.002 :      1.000]
Elapsed count f(      131,072):           131,072:      2.000 [     0.004 :      2.000]
Elapsed count f(      262,144):           262,144:      2.000 [     0.007 :      1.750]
Elapsed count f(      524,288):           524,288:      2.000 [     0.008 :      1.143]
Elapsed count f(    1,048,576):         1,048,576:      2.000 [     0.014 :      1.750]
Elapsed count f(    2,097,152):         2,097,152:      2.000 [     0.037 :      2.643]
Elapsed count f(    4,194,304):         4,194,304:      2.000 [     0.057 :      1.541]
Elapsed count f(    8,388,608):         8,388,608:      2.000 [     0.120 :      2.105]
Elapsed count f(   16,777,216):        16,777,216:      2.000 [     0.229 :      1.908]
Elapsed count f(   33,554,432):        33,554,432:      2.000 [     0.430 :      1.878]
Elapsed count f(   67,108,864):        67,108,864:      2.000 [     0.879 :      2.044]
Elapsed count f(  134,217,728):       134,217,728:      2.000 [     1.843 :      2.097]
Elapsed count f(  268,435,456):       268,435,456:      2.000 [     3.706 :      2.011]
Elapsed count f(  536,870,912):       536,870,912:      2.000 [     7.635 :      2.060]

N appends in linear time

Each append is amortized constant time

Java's StringBuffer is implemented with a resizing array.

Note: To see StringBuilder in action, see ResizingArrayQueue and ResizingArrayStack in package algs13.
They each have an implementation of Java's toString method that makes use of StringBuilder.