CS 3500 Day 13

Object Oriented Design

Today we're finally getting into performance, and how to make our programs faster using the proper Java classes.

String result = "";

for (...) {
    ...
    result += ...;
    ...
}

return result;

In the previous code example, we're adding something to a string. This is the efficiency of that:

efficiency

This is a very innefficient operation, with a poor runtime. We want something that can be added to quickly:

public interface StringAccumulator {
  /**
   * Appends the given character to the end of the accumulated string.
   *
   * @param c the character to append
   * @return a reference to {@code this} (for method chaining)
   */
  @Override
  StringAccumulator append(char c);

  /**
   * Returns the accumulated string value. Should be the same as
   * {@code #toString()}.
   *
   * @return the accumulated string value
   */
  String stringValue();
}

And using our implementation:

StringAccumulator result = new ...StringAccumulator();

for (...) {
    ...
    result.append(c);
    ...
}

return result.stringValue();

It's easy to write a string class that implements our interface, what's better though is an abstract array class whose growing we can determine:

public abstract class AbstractArrayStringAccumulator
  implements StringAccumulator
{
  private char[] contents = new char[INITIAL_CAPACITY];
  private int length = 0;

  /**
   * The initial array capacity.
   */
  public final static int INITIAL_CAPACITY = 10;

  @Override
  public final String stringValue() {
    return String.valueOf(contents, 0, length);
  }

  @Override
  public final String toString() {
    return stringValue();
  }

  @Override
  public final ArrayStringAccumulator append(char c) {
    ensureCapacity(length + 1);
    contents[length++] = c ;
    return this;
  }

  /**
   * Returns the current capacity of the string accumulator, after which
   * expansion will be necessary.
   *
   * @return the current capacity
   */
  public int capacity() {
    return contents.length;
  }

  public final void ensureCapacity(int minCapacity) {
    if (contents.length < minCapacity) {
      resize(determineNewCapacity(minCapacity));
    }
  }

  private void resize(int newCapacity) {
    contents = Arrays.copyOf(contents, newCapacity);
  }

  /**
   * Returns the capacity to expand to, given the requested minimum
   * capacity.
   *
   * @param minCapacity the requested minimum capacity
   * @return the capacity to expand to
   */
  protected abstract int determineNewCapacity(int minCapacity);
}

This implementation allows the programmer to determine how the accumulator will grow in size. This is basically a way to mock how many lists work in Java. Also mocking like this allows us to switch our strategy on the fly.

/**
 * A string accumulator class that always expands to exactly the
 * necessary size to hold the current accumulated character sequence.
 */
public final class ExactArrayStringAccumulator
  extends AbstractArrayStringAccumulator
{
  @Override
  protected int determineNewCapacity(int minCapacity) {
    return minCapacity;
  }
}

public final class LinearArrayStringAccumulator
  extends AbstractArrayStringAccumulator
{
  public static int DEFAULT_STEP = 16;

  @Override
  protected int determineNewCapacity(int minCapacity) {
    // (a + b - 1) / b computes ceil((double) a / b)
    return ((minCapacity + DEFAULT_STEP - 1) / DEFAULT_STEP) * DEFAULT_STEP;
  }
}

public final class DoublingArrayStringAccumulator
  extends AbstractArrayStringAccumulator
{
  @Override
  protected int determineNewCapacity(int minCapacity) {
    return Integer.max(minCapacity, capacity() * 2);
  }
}

public final class PreallocArrayStringAccumulator
  extends AbstractArrayStringAccumulator
{
  @Override
  protected int determineNewCapacity(int minCapacity) {
    return Integer.max(minCapacity, 100_000);
  }
}

Here's the efficiency when using these:

efficiency2

And if we want to look at only the fastest:

efficiency3

And finally compared to using a StringBuilder:

efficiency4