Проблема производительности в коде Scala - O (nlgn) быстрее, чем O (n)

Question

Я только начинаю с 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). Итак, я продолжил и реализовал это в моем 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)
}

Оказывается, первая версия работала быстрее, чем вторая. Теперь я совершенно не понимаю, что я мог сделать неправильно. Есть ли что-то в рекурсии во второй версии, которая вызывает большие накладные расходы?

Мне также хотелось бы получить предложение о том, каков идиоматический способ написания второго решения? Это мой первый серьезный опыт в функциональном программировании, и я изо всех сил пытаюсь написать функцию с хвостовой рекурсией.

Answer 1

Vector с значительно медленнее, чем Array с в целом . В частности

Vector постатейное построение в 5-15 раз медленнее, чем List или mutable.Buffer, и даже в 40 раз медленнее, чем предварительное выделение Array в тех случаях, когда это возможно.

С map и sorted длина массива известна, поэтому они могут быть предварительно выделены.

Как упоминается на этой странице, Vector#:+ действительно логарифмичен, так что в итоге вы получите O(n log n) в обоих случаях. Даже если вы этого не сделали, O(n log n) против O(n) технически говорит только о том, как изменяется производительность, когда ввод увеличивается бесконечно. Это в основном соответствует тому, что быстрее для небольших входов, но только в основном.

Мне также хотелось бы получить предложение о том, каков идиоматический способ написания второго решения?

Один из способов - построить List в обратном порядке, а затем обратить его в конце. Или используйте ArrayBuffer: даже если он изменчив, вы можете эффективно игнорировать это, поскольку нигде не сохраняете ссылку на старое состояние.