Есть ли способ ускорить это вычисление косинусного сходства между двумя двойными массивами в Java?

Question

У меня есть два двойных массива a и b, и я хочу вычислить косинусное сходство между ними.Мой код выглядит так:

double [][] target = new double [1][65000];
double [][] compare = new double [1][65000];

double dotProduct = dot(target[0], compare[0]);
double eucledianDist = norm2(target) * norm2(compare);
double output = dotProduct / eucledianDist;

private double norm2(double[][] a){
    double sum = 0;
    for (int i = 0; i < a[0].length; i++){
        sum = sum + a[0][i] * a[0][i];
    }
    return Math.sqrt(sum);
}

private double dot(double[] a, double [] b){
    double sum = 0;
    for(int i = 0; i < a.length; i ++){
        sum += a[i] * b[i];
    }
    return sum;
}

Есть ли способ ускорить время вычислений?

Answer 1

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

double computeSimilarity(double[] a, double[] b) {

  double dotProduct = 0;
  double normASum = 0; 
  double normBSum = 0;

  for(int i = 0; i + 3 < a.length; i++) {
      dotProduct += a[i] * b[i];
      normASum += a[i] * a[i];
      normBSum += b[i] * b[i];
      i++;
      dotProduct += a[i] * b[i];
      normASum += a[i] * a[i];
      normBSum += b[i] * b[i];
      i++;
      dotProduct += a[i] * b[i];
      normASum += a[i] * a[i];
      normBSum += b[i] * b[i];
      i++;
      dotProduct += a[i] * b[i];
      normASum += a[i] * a[i];
      normBSum += b[i] * b[i];
  }
  for( ; i < a.length; i ++) {
      dotProduct += a[i] * b[i];
      normASum += a[i] * a[i];
      normBSum += b[i] * b[i];
  }

  double eucledianDist = Math.sqrt(normASum) * Math.sqrt(normBSum);
  return dotProduct / eucledianDist;
}

Возможно, сохранение a[i] и b[i] во временных переменных может иметь небольшой эффект.

Answer 2

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

Что вы можете сделать, это попытаться объединить оба цикла в одной функции.

Что-то вроде:

double computeSimilarity(double[] a, double[] b) {
  //todo: you might want to check they are the same size before proceeding

  double dotProduct = 0;
  double normASum = 0; 
  double normBSum = 0;

  for(int i = 0; i < a.length; i ++) {
      dotProduct += a[i] * b[i];
      normASum += a[i] * a[i];
      normBSum += b[i] * b[i];
  }

  double eucledianDist = Math.sqrt(normASum) * Math.sqrt(normBSum);
  return dotProduct / eucledianDist;
}

Если вам действительно нужны 2 измерения, вызовите функцию вышев каждом измерении.Так что в вашем примере вы бы назвали это как computeSimilarity(target[0], compare[0]);

Answer 3

Для хорошего заказа версия Stream, как более выразительная и распараллеливаемая.

double computeSimilarity(final double[] a, final double[] b) {
    double normA = Math.sqrt(DoubleStream.of(a).parallel().map(x -> x * x).sum());
    double normB = Math.sqrt(DoubleStream.of(b).parallel().map(x -> x * x).sum());
    double dotProduct = IntStream.range(0, a.length).parallel()
            .mapToDouble(i -> a[i] * b[i]).sum();

    double eucledianDist = normA * normB;
    return dotProduct / eucledianDist;
}

Answer 4

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

Оттуда вы можете посмотреть на две вещи:

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

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

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