Java: Cache results of computation?

Question

I'm writing a program to calculate a value that is a measure of the similarity between two objects. The comparison is commutative, so compare(a, b) == compare(b, a).

The program's output to the console is a matrix of all results. However, since the matrix has each comparison twice ((a, b) and (b, a)), I'd like to save time by only calculating it once. What is the best way to cache these results?

Rough example of what the output looks like:

    a      b        c
a   0      20      9001

b  20      0      333

c  9001    333      0

Answer 1

It sounds like you're already caching the results really - in the matrix. Just compute one "triangle" of the matrix and fill in the rest from that:

// Compute one triangle
for (int i=0; i < size; i++)
{
    for (int j=0; j <= i; j++)
    {
        matrix[i][j] = computeValue(i, j);
    }
}

// Now mirror it
for (int i = 0; i < size; i++)
{
    for (int j = i + 1; j < size; j++)
    {
        matrix[i][j] = matrix[j][i];
    }
}

Answer 2

Calculate only one triangle, and make an access function like

get(int x, int y) {
  if (x > y) { return matrix[x][y] };
  return matrix[y][x];

Answer 3

As others have mentioned, you should just calculate one side of the triangle. You don't hove to copy it or even allocate space for it either. Just transform your x and y coordinates into a single index, and you can have an array that's a little over half the size of the full square matrix. eg:

class SymmetricMatrix {
  private final double[];

  /**
   * @param size the size of one dimension of the matrix. eg: 3 for a 3x3 matrix.
   */
  SymmetricMatrix(int size) {
    matrix = new double[index(size) + 1];
  }

  private index(int x, int y) {
    if (x > y) {
      int tmp = x;
      x = y;
      y = tmp;
    }
    // now x <= y
    i = (y * y + y) / 2 + x;
  }

  public double get(int x, int y) {
    return matrix[index(x, y)];
  }

  public void set(int x, int y, double value) {
    matrix[index(x, y)] = value;
  }
}

This example uses double values, but you can easily adjust that (or even make it generic, if you want to use objects).

To fill it in:

SymmetricMatrix matrix = new SymmetricMatrix(size);
for (int y = 0; y < size; y++) {
    for (int x = 0; x <= y; x++) {
        matrix.set(x, y, /* value */);
    }
}

Answer 4

Looks like you don't need it for this task but if you have an expensive function and need to cache the result there is a very good thread safe method here:

http://www.javaspecialists.eu/archive/Issue125.html

Answer 5

You need to be rather careful with caching results of methods like compareTo and equals.

If you have N array instances you potentially need to cache N^2 comparison results. (This is of course application dependent ...)

Also, if your application creates and discards large numbers of (matrix) instances, then you may end up with lots of entries in the cache, resulting in garbage retention problems. You can mitigate this with weak references, but they make garbage collection significantly slower.

If I was doing this, I'd first profile the application to determine if the compareTo and equals methods are really bottlenecks. Then if they were, I'd consider using something other than caching to speed up the methods; e.g. storing a lazily computed hash with each array could speed up equals.