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

Question

Я новичок в Scala и просто читал Scala By Example . В главе 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.

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