представление scala vs java для задачи «Min Steps in Infinite Grid» (закрыть)

Question

У меня 2 функции выполняют одинаковую логику в Scala и Java.

Я написал решение в Scala:

def coverPoints(A: Array[Int], B: Array[Int]): Int = {
    def diff(x1: Int, x2: Int, y1: Int, y2: Int): Int = Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2))

    @tailrec
    def coverPoints(total: Int, arr1: List[Int], arr2: List[Int]): Int =
      if (arr1.length <= 1) total else coverPoints(total + diff(arr1(0), arr1(1), arr2(0), arr2(1)), arr1.tail, arr2.tail)

    coverPoints(0, A.toList, B.toList)
  }

Но это решение достигает Time Limit Exceeded. Тогда я написал это с Java:

private int diff(int x1, int y1, int x2, int y2) {
    return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
}

public int coverPoints(int[] a, int[] b) {
    if (a == null || a.length <= 1) {
        return 0;
    }
    int distant = 0;
    for (int i = 0; i < a.length - 1; i++) {
        distant += diff(a[i], b[i], a[i + 1], b[i + 1]);
    }
    return distant;
}

Но система говорит мне, что производительность кода Scala недостаточно хороша. И Java проходит проверку производительности. Как можно оптимизировать производительность этой функции Scala?

Answer 1

Я не знаю, почему вы меняете параметры Array на List параметры.Индексирование списка arr1(1) и получение длины списка arr1.length являются линейными операциями.Обе эти операции выполняются в массиве намного быстрее.

Кроме того, вам вообще не нужно выполнять рекурсию.

def coverPoints(a: Array[Int], b: Array[Int]): Int =
  a.indices.init.fold(0){ case (acc,idx) =>
    acc + Math.max(Math.abs(a(idx) - a(idx+1)), Math.abs(b(idx) - b(idx+1)))
  }