时间戳

首页 > 解决方案 > Scala 代码中的性能问题 - O(nlgn) 比 O(n) 快

algorithm - Scala 代码中的性能问题 - O(nlgn) 比 O(n) 快

问题描述

我刚刚开始使用 scala。我试图通过解决 leetcode 上的简单问题来学习它。这是我在LC #977的第一次（成功）尝试：

def sortedSquares(A: Array[Int]): Array[Int] = {
    A.map(math.abs).map(x => x * x).sorted
}

由于排序，我希望这是运行O(NlgN)时间，N即输入数组的大小。但我知道这个问题有一个两点解决方案，它的运行时复杂度为O(N). 所以我继续在我的菜鸟 Scala 中实现了它：

def sortedSquaresHelper(A: Array[Int], result: Vector[Int], left: Int, right: Int): Array[Int] = {
    if (left < 0 && right >= A.size) {
        result.toArray
    } else if (left < 0) {
        sortedSquaresHelper(A, result :+ A(right) * A(right), left, right + 1)
    } else if (right >= A.size) {
        sortedSquaresHelper(A, result :+ A(left) * A(left), left - 1, right)
    } else {
        if (math.abs(A(left)) < math.abs(A(right))) {
            sortedSquaresHelper(A, result :+ A(left) * A(left), left - 1, right)
        } else {
            sortedSquaresHelper(A, result :+ A(right) * A(right), left, right + 1)
        }
    }
}

def sortedSquares(A: Array[Int]): Array[Int] = {
    val min_idx = A.zipWithIndex.reduceLeft((x, y) => if (math.abs(x._1) < math.abs(y._1)) x else y)._2
    val result: Vector[Int] = Vector(A(min_idx) * A(min_idx))
    sortedSquaresHelper(A, result, min_idx - 1, min_idx + 1)
}

事实证明，第一个版本比第二个版本运行得更快。现在我很困惑我可能做错了什么。第二版本中的递归是否存在导致高开销的问题？

我还想要一些关于编写第二个解决方案的惯用 scala 方式的建议？这是我第一次认真尝试函数式编程，我正在努力以尾递归的方式编写函数。

标签： algorithmscalafunctional-programming

解决方案

Vectors总体上比 s 慢得多Array。尤其

Vector逐项构造比构造慢 5-15 倍List，在可能的情况下mutable.Buffer甚至比预分配慢 40 倍。Array

map数组的长度和长度sorted是已知的，因此可以预先分配它们。

正如该页面所提到的，Vector#:+它实际上是对数的，所以你最终O(n log n)在这两种情况下都会得到。即使您没有，从技术上讲， O(n log n)vs也O(n)只能说明当输入无限增长时性能如何变化。它主要与小输入更快的方法一致，但仅在大多数情况下。

我还想要一些关于编写第二个解决方案的惯用 scala 方式的建议？

一种方法是以List相反的顺序构造 a ，然后在最后将其反转。或者使用ArrayBuffer: 即使它是可变的，您也可以有效地忽略它，因为您不会在任何地方保留对旧状态的引用。

推荐阅读