时间戳

首页 > 解决方案 > scala 与 java 在“无限网格中的最小步数”问题中的性能（关闭）

java - scala 与 java 在“无限网格中的最小步数”问题中的性能（关闭）

问题描述

我有 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 函数的性能？

标签： javascala

解决方案

我不知道您为什么要将参数更改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)))
  }

推荐阅读