Java: кешировать результаты вычислений?

Question

Я пишу программу для вычисления значения, которое является мерой сходства между двумя объектами. Сравнение коммутативное, so compare(a, b) == compare(b, a).

Вывод программы на консоль представляет собой матрицу всех результатов. Однако, так как в матрице есть каждое сравнение дважды ((a, b) и (b, a)), я бы хотел сэкономить время, рассчитав его только один раз. Каков наилучший способ кэширования этих результатов?

Грубый пример того, как выглядит результат:

    a      b        c
a   0      20      9001

b  20      0      333

c  9001    333      0

Answer 1

Похоже, вы уже кешируете результаты действительно - в матрице. Просто вычислите один «треугольник» матрицы и заполните оставшееся значение:

// 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

Как уже упоминали другие, вы должны просто рассчитать одну сторону треугольника. Вы не должны копировать его или даже выделять для него место. Просто преобразуйте свои координаты x и y в один индекс, и вы можете получить массив, который чуть больше половины размера полного квадратная матрица например:

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;
  }
}

В этом примере используются двойные значения, но вы можете легко настроить их (или даже сделать их общими, если хотите использовать объекты).

Для заполнения:

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 3

Вы должны быть довольно осторожны с результатами кэширования таких методов, как compareTo и equals.

Если у вас есть N экземпляров массива, вам может понадобиться кэшировать N ^ 2 результатов сравнения. (Это, конечно, зависит от приложения ...)

Кроме того, если ваше приложение создает и отбрасывает большое количество (матричных) экземпляров, то вы можете получить много записей в кэше, что приведет к проблемам с удержанием мусора. Вы можете смягчить это с помощью слабых ссылок, но они значительно замедляют сборку мусора.

Если бы я делал это, я бы сначала профилировал приложение, чтобы определить, действительно ли методы compareTo и equals являются узкими местами. Тогда, если бы они были, я бы подумал об использовании чего-то кроме кэширования для ускорения методов; например хранение лениво вычисленного хэша с каждым массивом может ускорить equals.

Answer 4

Похоже, вам не нужно это для этой задачи, но если у вас дорогая функция и вам нужно кэшировать результат, здесь есть очень хороший потокобезопасный метод:

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

Answer 5

Рассчитайте только один треугольник и создайте функцию доступа, такую ​​как

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