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