Scala Performance: императив против функционального стиля

Question

Я новичок в Scala и просто читал Scala By Example. В главе 2 у автора есть 2 разные версии быстрой сортировки.

Одним из них является императивный стиль:

def sort(xs: Array[Int]) {
    def swap(i: Int, j: Int) {
        val t = xs(i); xs(i) = xs(j); xs(j) = t
    }
    def sort1(l: Int, r: Int) {
        val pivot = xs((l + r) / 2)
        var i = l; var j = r
        while (i <= j) {
            while (xs(i) < pivot) i += 1
            while (xs(j) > pivot) j -= 1
            if (i <= j) {
                swap(i, j)
                i += 1
                j -= 1
            }
        }
        if (l < j) sort1(l, j)
        if (j < r) sort1(i, r)
    }
    sort1(0, xs.length - 1)
}

Одним из них является функциональный стиль:

def sort(xs: Array[Int]): Array[Int] = {
  if (xs.length <= 1) xs
  else {
    val pivot = xs(xs.length / 2)
    Array.concat(
      sort(xs filter (pivot >)),
           xs filter (pivot ==),
      sort(xs filter (pivot <)))
  }
}

Очевидным преимуществом функционального стиля перед императивным является лаконичность. Но как насчет производительности? Поскольку он использует рекурсию, платим ли мы за снижение производительности так же, как и в других императивных языках, таких как C? Или, поскольку Scala является гибридным языком, предпочтительным является "путь Scala" (функциональный), что делает его более эффективным.

Примечание: автор упомянул, что функциональный стиль использует больше памяти.

Answer 1

Это зависит. Если вы посмотрите на исходники Scala, часто существует императивный стиль, используемый "под капотом", чтобы быть быстрым, но во многих случаях именно эти настройки позволяют вам писать функциональный функциональный код. Поэтому обычно вы можете придумать функциональное решение, которое достаточно быстро, но вы должны быть осторожны и знать, что вы делаете (особенно в отношении ваших структур данных). Например, массив concat во втором примере не очень хорош, но, вероятно, не так уж и плох - но использование списков здесь и объединение их с::: было бы излишним.

Но это не более чем догадки, если вы на самом деле не измеряете производительность. В сложных проектах очень сложно предсказать производительность, особенно когда такие вещи, как создание объектов и вызовы методов, все более оптимизируются компилятором и JVM.

Я бы предложил начать с функционального стиля. Если это слишком медленно, профилируйте это. Обычно есть лучшее функциональное решение. Если нет, вы можете использовать императивный стиль (или сочетание обоих) в качестве последнего средства.