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

Question

Я новичок в Scala и просто читал Scala By Example. В главе 2 автор имеет две разные версии Quicksort.

Одним из них является обязательным стиль:

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 way» (функциональный), тем самым более эффективным.

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

Answer 1

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

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

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