CODEWITHSUNDEEP
algorithmscalafunctional-programming
Shakkhar
Shakkhar

Reputation: 189

Performance issue in Scala code - O(nlgn) faster than O(n)

I am just getting started with scala. I am trying to learn it by solving easy problems on leetcode. Here's my first (successful) attempt at LC #977:

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

Because of the sorting, I expected this to run O(NlgN) time, N being the size of the input array. But I know that there is a two-pointers solution to this problem which has a run-time complexity of O(N). So I went ahead and implemented that in my noob 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)
}

Turns out, the first version ran faster than the second one. Now I am quite confused about what I might have gotten wrong. Is there something about the recursion in second version that is causing high overhead?

I'd also like some suggestion about what is the idiomatic scala-way of writing the second solution? This is my first serious foray into functional programming, and I am struggling to write the function in a tail-recursive manner.

Upvotes: 0

Views: 97

Answers (1)

Alexey Romanov
Alexey Romanov

Reputation: 170735

Vectors are significantly slower than Arrays overall. In particular

Vector item-by-item construction is 5-15x slower than List or mutable.Buffer construction, and even 40x slower than pre-allocating an Array in the cases where that's possible.

With map and sorted length of array is known, so they can be preallocated.

As that page mentions, Vector#:+ is really logarithmic, so you end up with O(n log n) in both cases. Even if you didn't, O(n log n) vs O(n) technically only says something about how performance changes when input grows indefinitely. It's mostly aligned with what's faster for small inputs as well, but only mostly.

I'd also like some suggestion about what is the idiomatic scala-way of writing the second solution?

One way is to construct a List in the reverse order, and then reverse it at the end. Or use an ArrayBuffer: even though it's mutable, you can effectively ignore that because you don't keep a reference to the older state anywhere.

Upvotes: 1

Related Questions