2017-02-21-CS-3500-Day-13.mdx

archived	title	date	description	tags	draft	project
true	CS 3500 Day 13	2017-02-21	Object Oriented Design	OOD java notes	false	OOD

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:

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:

And if we want to look at only the fastest:

And finally compared to using a StringBuilder: