4

我遇到了 Scala 和 Java 性能之间非常奇怪的差异。我已经在 J​​ava 中实现了一个反转计数例程，然后将其逐行移植到 Scala，因为所有惯用的 Scala 版本（使用Listor Stream）要么非常慢，要么因堆栈溢出/内存不足错误而崩溃。但是这个版本也很慢——Java 版本处理 100000 个整数的数组需要 22 毫秒，而 Scala 版本需要 3 秒。以下是 Scala 版本的相关代码：

  def mergeAndCountInversions(xs: Array[Int], aux: Array[Int], left: Int, right: Int) = {
    xs.copyToArray(aux)
    val m = left + (right - left) / 2

    var i = left
    var j = m + 1
    var inv: Long = 0

    for (k <- left to right) {
      if (i > m) {
        xs(k) = aux(j)
        j += 1
      } else if (j > right) {
        xs(k) = aux(i)
        i += 1
      } else if (aux(j) < aux(i)) {
        xs(k) = aux(j)
        j += 1
        inv += (m - i) + 1
      } else {
        xs(k) = aux(i)
        i += 1
      }
    }
    inv
  }

有关如何提高此例程性能的任何想法？

UPD：Scala 版本的性能不佳完全是我的错。第一条语句不必要地将整个数组复制到辅助数组。当更改为仅复制所需部分时，性能与 Java 应有的水平相当。

4

1 回答 1

1

很可能是因为理解力。它被脱糖

Range(left, right).foreach { k =>
  // code...
}

为了使其与 Java 解决方案具有可比性，您必须将其替换为 while 循环。

var k = left

while (k <= right) {
  // code...

  k += 1
}

我很确定，这个解决方案将与 Java 版本相提并论。

于 2013-09-23T12:36:36.187 回答