Hiệu suất Scala: bắt buộc so với kiểu chức năng

Question

Tôi mới sử dụng Scala và chỉ đọc Scala By Example. Trong chương 2, tác giả có 2 phiên bản Quicksort khác nhau.

Một là bắt buộc phong cách:

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) 
} 

Một là chức năng phong cách:

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 <))) 
    } 
} 

Lợi thế rõ ràng là phong cách chức năng có hơn phong cách bắt buộc là conciseness. Nhưng những gì về hiệu suất? Kể từ khi nó sử dụng đệ quy, chúng ta phải trả tiền cho các hình phạt hiệu suất giống như chúng tôi làm trong các ngôn ngữ mệnh lệnh khác như C? Hoặc, Scala là một ngôn ngữ lai, "cách Scala" (chức năng) được ưa thích, do đó hiệu quả hơn.

Lưu ý: Tác giả đã đề cập đến kiểu chức năng sử dụng nhiều bộ nhớ hơn.

Answer 1

Điều đó tùy thuộc. Nếu bạn nhìn vào các nguồn Scala, thường có một phong cách bắt buộc được sử dụng "dưới mui xe" để có thể thực hiện - nhưng trong nhiều trường hợp chính xác những điều chỉnh này cho phép bạn viết performant chức năng mã. Vì vậy, thông thường bạn có thể đưa ra một giải pháp chức năng đủ nhanh, nhưng bạn phải cẩn thận và biết những gì bạn làm (đặc biệt là liên quan đến cấu trúc dữ liệu của bạn). Ví dụ. mảng concat trong ví dụ thứ hai không đẹp, nhưng có lẽ không quá tệ - nhưng việc sử dụng Lists ở đây và concat chúng với ::: sẽ là quá mức cần thiết.

Nhưng đó không phải là nhiều hơn đoán được giáo dục nếu bạn không thực sự đo hiệu suất. Trong các dự án phức tạp, thật khó để dự đoán hiệu suất, đặc biệt là những thứ như tạo đối tượng và các cuộc gọi phương thức ngày càng được tối ưu hóa bởi trình biên dịch và JVM.

Tôi khuyên bạn nên bắt đầu với phong cách chức năng. Nếu nó quá chậm, hãy cấu hình nó. Thông thường có một giải pháp chức năng tốt hơn. Nếu không, bạn có thể sử dụng phong cách bắt buộc (hoặc kết hợp cả hai) như một phương sách cuối cùng.